After having beaten Michael Schumacher in F1 and Garry Kasparov in chess, Chuck Norris has decided to beat Petr in an ACM contest.
An ACM contest is a problem solving contest where each participant is given the same set of numProblems problems. A participant's score consists of two components: the number of problems he has solved so far, and the penalty time he has accumulated. Initially, both of those values are zero. At any time, a participant may submit a solution to a problem. This solution is tested against all the test cases prepared by the contest jury. If it doesn't pass all the test cases, the submission is considered wrong, and the participant's score does not change. If it passes all the test cases, then it is considered solved - the number of problems solved by the participant increases by 1 and his penalty increases by T + 20 * R, where T is the time of the correct submission (rounded up to the nearest minute) and R is the number of wrong submissions by that participant for that problem. After a participant solves a problem successfully, he is not allowed to submit any more solutions for that problem.
Participants are ranked as follows. If participant A has solved N1 problems and his penalty is P1, and participant B has solved N2 problems and his penalty is P2, then participant A's score is considered strictly better than participant B's score (i.e., A is ranked higher than B) if N1 > N2 or (N1 = N2 and P1 < P2).
For any problem, Chuck is able to produce a successful solution immediately. However, he doesn't want to solve all the problems immediately because it will reveal his superhuman abilities. Fortunately, he is also able to purposefully produce a failing solution to any problem immediately. Therefore Chuck has decided to divide the whole contest into n parts. These parts are described by the int partTimes containing exactly n elements. The first part consists of minutes 1 through partTimes, inclusive, the second part consists of minutes partTimes+1 through partTimes, inclusive, and so on. The n-th part consists of minutes partTimes[n-2]+1 through partTimes[n-1], inclusive, and the whole contest lasts exactly partTimes[n-1] minutes. He can submit any number of solutions during each part of the contest, and he can even submit multiple solutions within the same minute. He has given himself a set of restrictions that he must follow. These restrictions are given in the Strings lowerBounds and upperBounds, each of which contains exactly n elements, where each element is formatted "problems_solved penalty" (quotes for clarity), where both problems_solved and penalty are integers without extra leading zeros. Chuck wants his score immediately after the i-th part (0-based) to be strictly better than the score described in lowerBounds[i] and strictly worse than the result described in upperBounds[i].
Of course, Chuck wants his score at the end of the contest to be as good as possible while adhering to the given constraints. Return this best possible score as a String formatted "problems_solved penalty" (quotes for clarity), where problems_solved and penalty contain no extra leading zeroes. If it's not possible to follow all the given constraints, return an empty String instead.