H - Three Types of Coins Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 6 点

問題文

高橋君は 0 枚の金貨、 10^9 枚の銀貨、および X 枚の銅貨を持っています。

お店に N 個の袋が売られています。 i = 1, 2, \ldots, N について、i 個目の袋は A_i 枚の銀貨と B_i 枚の銅貨を支払うことで買うことができます。また、i 個目の袋の中には C_i 枚の金貨が入っており、袋を買うことでその中の金貨を手に入れることができます。

金貨 1 枚には 10^{100^{100}} 円の、銀貨 1 枚には 10^{100} 円の、銅貨 1 枚には 1 円の価値があります。 高橋君は N 個の袋のうち好きな個数（ 0 個でも良い）の袋を買い、最終的に持っている金貨、銀貨、銅貨の価値の合計を最大にしたいです。 最終的に持っている金貨、銀貨、銅貨の価値の合計が最大となるときの、金貨、銀貨、銅貨の枚数をそれぞれ出力してください。

袋を購入するために必要な銅貨や銀貨を他の種類の硬貨で代用することはできません。 例えば、銀貨 1 枚は円に換算したときには銅貨 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 番目の袋と 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

Score : 6 points

Problem Statement

Takahashi has 0 gold coins, 10^9 silver coins, and X bronze coins.

A shop sells N bags. For i = 1, 2, \ldots, N, the i-th bag can be bought by paying A_i silver coins and B_i bronze coins. The i-th bag contains C_i gold coins; by buying the bag, he obtains the gold coins in it.

A gold coin is worth 10^{100^{100}} yen (the currency in Japan), a silver coin is worth 10^{100} yen, and a bronze coin is worth 1 yen. Takahashi wants to buy some (possibly zero) of the N bags and maximize the resulting total value of the gold, silver, and bronze coins he has. Print the numbers of gold, silver, and bronze coins, when the resulting total value of the gold, silver, and bronze coins is maximized.

The bronze and silver coins required for buying a bag cannot be substituted by another kind of coin. For example, a silver coin is worth 10^{100} bronze coins when converted into yen, but it does not mean you can pay a silver coin instead of paying bronze coins.

Constraints

  • 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
  • All values in input are integers.

Input

Input is given from Standard Input in the following format:

N X
A_1 B_1 C_1
A_2 B_2 C_2
\vdots
A_N B_N C_N

Output

Print the numbers of gold coins P, silver coins Q, and bronze coins R, when the resulting total value of the gold, silver, and bronze coins is maximized. The numbers should be printed in the following format, separated by spaces:

P Q R

Sample Input 1

5 4
2 2 3
2 2 2
3 1 2
1 3 1
1 2 2

Sample Output 1

5 999999997 0

If Takahashi buys the 1-st and 5-th bags, he will pay A_1+A_5 = 2 + 1 = 3 silver coins and B_1+B_5 = 2 + 2 = 4 bronze coins, and obtain C_1+C_5 = 3 + 2 = 5 gold coins. As a result, he will have 5 gold coins, 10^9-3 silver coins, and 0 bronze coins, for a total value of 5 \times 10^{100^{100}} + (10^9-3) \times 10^{100} + 0 \times 1 yen, which is maximum possible.

Sample Input 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

Sample Output 2

92 999999930 0