Your team has already finished the ECOO Provincials, but you aren't sure if you are winning or not!
A team's score on the ECOO is computed in a somewhat unorthodox manner. Each of the problems, numbered from to , is worth up to points each. The contest is minutes long, and for each submission to a problem, a team earns a time bonus of points if their submission earns a non-zero number of points, where is a given integer number of minutes. denotes the ceiling function, which returns the smallest integer that is greater than or equal to . To simplify, all teams will make up to one submission to each problem.
You are given the points earned and the submission times of each problem for your team and another team. Your team has made submissions to all problems while the other team has only made submissions to the first problems. At what time from the start of the contest will you win the contest for sure? You win the contest for sure at a given time if the other team cannot possibly achieve your team's score or higher, ignoring all future events.
However, your eyesight is worsening, and you can't see the scoreboard very well. During the contest, you will make corrections. For each correction, you notice that you were wrong about the one of the existing submissions, so you correct your information about that submission. Each time, you want to know the new time in which your team is guaranteed to win. Corrections will persist.
For all subtasks,
|3||60||No additional constraints.|
The first line will contain , , , , , and .
lines of input follow. The line will contain and , two non-negative integers specifying the number of points your team earned, and the submission time for the problem.
lines of input follow. The line will contain and , two non-negative integers specifying the number of points the other team earned, and the submission time for the problem.
lines of input follow. Each line will contain four space separated integers in the form
c n p t.
- represents the submission team: for your team or for the other team.
- is the problem number of the submission. If , then . If , then .
- and represent corrected points earned and submission time, respectively, of the given submission.
Output lines. Before the first correction and after each correction, output on a new line the earliest integer time in minutes from the start of the contest in which you are guaranteed to win. If this time is greater than or if your team cannot win, print
4 3 2 110 180 5 110 20 85 96 90 49 38 112 110 60 60 24 51 89 1 2 42 53 2 1 33 44
150 bamboozled 112