|
||||||||||
ExamTime Limit: 6000/5500 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 171 Accepted Submission(s): 49 Problem Description You have to take $n$ exams, the exam $i$ was held in two periods of time, [$a$, $a$ + $at$] and [$b$, $b$ + $bt$] and you can take any one of the two periods to pass exam $i$. But note that you cannot take two different exams at the same time. For example, it is impossible to take the first exam at $[3,5]$ and take the second exam at $[5,8]$. \textbf{And note that for one exam}, the two periods of time may intersect, that is, $[a,\ a+at] \cap [b,\ b+bt] \ne \emptyset$ is also possible. Now, you want to pass all the $n$ exams as soon as possible. Print the earlist time when the last exam was finished if you can pass all the $n$ exams or print $-1$ if you can not pass all the exams. Input The first line contains a single integer $T$ denoting the number of test cases. For each test case, the first line contains a single integer $n$ ($1\leq n \leq 25000$). The next $n$ lines contain four integers each: $a$, $at$, $b$, $bt$ ($0\leq a,\ at,\ b,\ bt \leq 10^{9}$ and $\sum n \le 10^5$) Output For each test case, output the only line containing just one integer denoting the answer if there would be, or $-1$ otherwise. Sample Input
Sample Output
Source | ||||||||||
|