Exam

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

4
2
1 5 5 10
1 3 7 2
3
5 0 13 0
1 0 5 0
1 0 7 0
3
10 7 40 1
40 5 80 15
10 20 80 6
3
1 0 2 0
1 0 2 0
1 0 2 0

Sample Output

9
7
86
-1

Source

2020 Multi-University Training Contest 5