AT_past202209_h.３種の硬貨

高桥有 $0$ 枚金币，$10^9$ 枚银币，和 $X$ 枚铜币。

商店一共出售 $N$ 个包裹。对于 $i=1,2,\ldots,N$，第 $i$ 个包裹可以通过支付 $A_i$ 枚银币和 $B_i$ 枚铜币购买。第 $i$ 个包裹中包含 $C_i$ 枚金币，购买该包裹后即可获得其中的金币。

一枚金币价值 $10^{100^{100}}$ 日元（一种日本的货币），一枚银币价值 $10^{100}$ 日元，一枚铜币价值 $1$ 日元。高桥希望购买一些（可能为零）包裹，使他最终持有的金币、银币、铜币的总价值最大。请输出在使总价值最大时高桥所拥有的金币、银币、铜币的数量。

购买包裹时所需要的铜币和银币不能用其他种类的硬币代替。例如，虽然一枚银币在日元中相当于 $10^{100}$ 枚铜币，但这并不意味着你可以用一枚银币来支付铜币。

输入通过标准输入给出，格式如下：

$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

如果高桥购买了第 $1$ 个和第 $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$ 日元，这是最大可能的总价值。

数据范围

• $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$
• 所有输入数均为整数。

由 ChatGPT 5 翻译