不离(Never Leave)

题目描述

乱玄黄时序，探风林实虚。
我要你共我奇谈怪趣。
任日月斑斓，待春秋兴残。
我要我们有聚无散。

——银临《不离》

这道题目来自 zxy 哔哔，咕咕让哔哔选一首歌作为题目名，但是哔哔说没有想好，于是咕咕就帮他选了这首歌。

哔哔在玩一款叫做《暗黑破坏神》的游戏，某天哔哔灵光乍现，以游戏为背景出了一道神仙题并告诉了咕咕。咕咕并不会做，于是对题目进行了一定的简化。因此，经过简化后，这道题已经和《暗黑破坏神》没什么关系了。

游戏中人物有两个属性，我们分别称之为「力量」和「精神」，同时哔哔有 $n$ 件装备，穿戴第 $i$ 件装备需要人物在穿戴前的力量值不低于 $a_i$，精神值不低于 $b_i$。在穿戴第 $i$ 件装备后，人物的力量值会增加 $c_i$，精神值会增加 $d_i$。

哔哔可以自由选择穿装备的顺序，只要满足力量和精神不低于对应值，就可以穿戴该装备。

现在，咕咕想知道，如果想让哔哔穿戴上所有的装备，那么人物的初始力量值（即没有穿任何装备之前的力量值）最小应该是多少？在初始力量值最小的前提下，初始精神值（即没有穿任何装备之前的精神值）最小应该是多少？

显然，初始力量和初始精神都应该是非负整数。

输入格式

第一行有一个整数，表示该测试点所在的子任务编号 $T$。
第二行有一个整数，表示哔哔的装备件数 $n$。
第 $3$ 到第 $(n+2)$ 行，每行四个整数，第 $(i+2)$ 行的整数依次表示 $a_i,b_i,c_i,d_i$。

输出格式

输出一行两个用空格隔开的整数，分别表示最小的初始力量值以及在初始力量值最小的前提下最小的初始精神值。

样例输入 #1

0
2
1 5 0 2
1 2 3 4

样例输出 #1

1 2

数据范围

样例 1 解释

当初始力量值为 $1$，精神值为 $2$ 时，可以穿戴第 $2$ 件装备。在穿戴该装备后，增加 $3$ 点力量和 $4$ 点精神，人物的属性变为 $4$ 点力量和 $6$ 点精神，此时可以穿戴第 $1$ 件装备。

数据规模与约定

本题采用多测试点捆绑测试。

• 子任务 $1$（$5$ 分）：保证 $n=0$。
• 子任务 $2$（$5$ 分）：保证 $n=1$。
• 子任务 $3$（$20$ 分）：保证 $a_i,b_i \le 100$，$n \le 6$。
• 子任务 $4$（$10$ 分）：保证 $a_i,b_i \le 10^5$，$n \le 6$。
• 子任务 $5$（$10$ 分）：保证 $a_i,b_i \le 10$。
• 子任务 $6$（$10$ 分）：保证 $a_i,b_i \le 100$。
• 子任务 $7$（$10$ 分）：保证 $b_i=0$，$n \le 6$。
• 子任务 $8$（$10$ 分）：保证 $b_i=0$。
• 子任务 $9$（$10$ 分）：保证 $n \le 6$。
• 子任务 $10$（$10$ 分）：无特殊约定。

对于全部的测试点，保证 $0 \le n \le 10^5$，$0 \le a_i,b_i,c_i,d_i \le 10^9$。

知识点与难度

本题涉及的知识点从属于 CSP-S，难度（CF Rating）：1700。

测试点分布

出处：原题链接