Description

This problem comes from zxy's chatting. Gugu asked Bibi to choose a song as the title, but Bibi said he had not decided yet, so Gugu picked this song for him.

Bibi is playing a game called Diablo. One day, Bibi suddenly got an idea, made a very difficult problem using the game as the background, and told it to Gugu. Gugu could not solve it, so he simplified the problem a bit. Therefore, after simplification, this problem has almost nothing to do with Diablo.

In the game, the character has two attributes, which we call "Strength" and "Spirit". Bibi has $n$ pieces of equipment. To equip the $i$-th piece, before equipping it, the character's Strength must be at least $a_i$, and Spirit must be at least $b_i$. After equipping the $i$-th piece, the character's Strength increases by $c_i$, and Spirit increases by $d_i$.

Bibi can choose the order of equipping freely. As long as Strength and Spirit are not less than the required values, he can equip that piece.

Now, Gugu wants to know: if Bibi wants to equip all pieces of equipment, what is the minimum initial Strength (i.e., the Strength before equipping anything)? Under the condition that the initial Strength is minimal, what is the minimum initial Spirit (i.e., the Spirit before equipping anything)?

Clearly, both the initial Strength and the initial Spirit should be non-negative integers.

Input Format

The first line contains an integer $T$, which denotes the subtask number of this test point.
The second line contains an integer $n$, which denotes the number of pieces of equipment Bibi has.
Lines $3$ to $(n+2)$ each contain four integers. On line $(i+2)$, the integers are $a_i, b_i, c_i, d_i$ in order.

Output Format

Output one line with two integers separated by a space, representing the minimum initial Strength, and the minimum initial Spirit under the condition that the initial Strength is minimal.

0
2
1 5 0 2
1 2 3 4

1 2

Hint

Explanation for Sample 1

When the initial Strength is $1$ and the Spirit is $2$, you can equip the $2$-nd piece of equipment. After equipping it, Strength increases by $3$ and Spirit increases by $4$, so the attributes become $4$ Strength and $6$ Spirit. Then you can equip the $1$-st piece of equipment.

Constraints

This problem uses bundled testdata with multiple test points.

• Subtask $1$ ($5$ points): guaranteed $n=0$.
• Subtask $2$ ($5$ points): guaranteed $n=1$.
• Subtask $3$ ($20$ points): guaranteed $a_i, b_i \le 100$, $n \le 6$.
• Subtask $4$ ($10$ points): guaranteed $a_i, b_i \le 10^5$, $n \le 6$.
• Subtask $5$ ($10$ points): guaranteed $a_i, b_i \le 10$.
• Subtask $6$ ($10$ points): guaranteed $a_i, b_i \le 100$.
• Subtask $7$ ($10$ points): guaranteed $b_i=0$, $n \le 6$.
• Subtask $8$ ($10$ points): guaranteed $b_i=0$.
• Subtask $9$ ($10$ points): guaranteed $n \le 6$.
• Subtask $10$ ($10$ points): no special constraints.

For all test points, it is guaranteed that $0 \le n \le 10^5$, $0 \le a_i, b_i, c_i, d_i \le 10^9$.

Hint

There are $4$ sample files. Please see forever.zip in the additional files.

For the third sample, $b_i = 0$.

Translated by ChatGPT 5