P7095 [yLOI2020] Never Apart

> In chaotic time, I seek what is real and what is false in the wind and forest. > I want you to share strange talks and odd fun with me. > Let the sun and moon be colorful, and let spring and autumn rise and fall. > I want us to gather and never part. — Yin Lin, *Never Apart*.

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.

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 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.

### 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