← 返回题目列表

AtCoder · past202209_h

H. 三种硬币

中文机器翻译题面 查看原题

分数: 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