分数: 6 点
问题陈述
高桥有 0 金币, 10^9 银币,以及 X 铜币。
某商店有卖 N 袋。 对于 i = 1, 2, \ldots, N, i第个包可以通过付费购买 A_i 银币和 B_i 铜币。 的 i第袋包含 C_i 金币;通过购买袋子,他可以获得里面的金币。
一枚金币值 10^{100^{100}} 日元(日本货币),一枚银币值 10^{100} 日元,铜币价值 1 日元。 高桥想购买一些(可能是零) N 袋子并最大化他所拥有的金币、银币和铜币的总价值。 当金、银、铜币的总价值最大时,打印金、银、铜币的数量。
购买包所需的铜币和银币不能用其他硬币替代。 例如,一枚银币的价值 10^{100} 铜币兑换成日元后,并不意味着可以用银币代替支付铜币。
约束
- 1 \leq N \leq 3000
- 0 \leq X \leq 3000
- 0 \leq A_i, B_i \leq 3000
- 1 \leq A_i + B_i
- 1 \leq C_i \leq 3000
- 输入中的所有值都是整数。
输入
输入由标准输入按以下格式给出:
N X A_1 B_1 C_1 A_2 B_2 C_2 \vdots A_N B_N C_N
输出
打印金币数量 P,银币 Q和铜币 R,当金币、银币和铜币的总价值最大化时。 数字应按以下格式打印,并用空格分隔:
P Q R
示例输入 1
5 4 2 2 3 2 2 2 3 1 2 1 3 1 1 2 2
示例输出 1
5 999999997 0
如果高桥购买了 1-st 和 5第袋,他会付钱 A_1+A_5 = 2 + 1 = 3 银币和 B_1+B_5 = 2 + 2 = 4 铜币,并获得 C_1+C_5 = 3 + 2 = 5 金币。 结果,他将拥有 5 金币, 10^9-3 银币,以及 0 铜币,总价值为 5 \times 10^{100^{100}} + (10^9-3) \times 10^{100} + 0 \times 1 日元,这是最大可能的。
示例输入 2
20 50 4 3 7 2 0 8 7 2 4 9 0 9 6 5 8 4 7 1 3 9 2 3 9 2 7 4 4 2 7 3 6 3 2 4 10 8 2 2 10 8 1 5 3 2 6 3 8 5 8 1 9 3 7 4 9 6 2 5 6 7
示例输出 2
92 999999930 0