C - 工場の利益最大化 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 366 点

問題文

高橋君は工場を経営しており、N 種類の製品を製造・販売することで利益を得ています。

工場には M 台の製造機械があります。各機械の稼働可能時間はいずれも K 分間であり、各機械で製造する製品の製造時間の合計は K 分以下でなければなりません。

各製品 i（1 \leq i \leq N）には以下の情報が与えられます：

  • C_i：製品 i を 1 つ製造するための原材料コスト（円）
  • T_i：製品 i を 1 つ製造するのに必要な時間（分）
  • P_i：製品 i を 1 つ販売したときの売値（円）

製品 i を 1 つ製造して販売すると、P_i - C_i 円の利益が得られます（この値が負の場合は損失となります）。

各機械は一度に 1 つの製品しか製造できず、製品の製造を途中で中断することはできません。1 つの製品の製造が完了したら、切り替え時間なしですぐに次の製品の製造を開始できます。

M 台の機械はそれぞれ独立に動作します。原材料は十分にあり、どの種類の製品も個数の上限なく製造できます。各機械で製造する製品の種類と個数は機械ごとに自由に決めることができ、同じ種類の製品を複数の機械で製造することもできます。

また、ある機械で製品を 1 つも製造しないことも許されます。製品を 1 つも製造しなかった機械からの利益は 0 円です。

M 台すべての機械から得られる利益の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 500
  • 1 \leq M \leq 10^9
  • 1 \leq K \leq 200{,}000
  • 1 \leq C_i \leq 10^6（1 \leq i \leq N）
  • 1 \leq T_i \leq K（1 \leq i \leq N）
  • 1 \leq P_i \leq 10^6（1 \leq i \leq N）
  • 入力はすべて整数である。
  • 答えは 2^{63} - 1（= 9{,}223{,}372{,}036{,}854{,}775{,}807、64 ビット符号付き整数の最大値）以下であることが保証される。

入力

N M K
C_1 T_1 P_1
C_2 T_2 P_2
\vdots
C_N T_N P_N
  • 1 行目には、製品の種類数 N、機械の台数 M、各機械の稼働可能時間（分）K が、空白区切りで与えられる。
  • 続く N 行のうち i 行目（1 \leq i \leq N）には、製品 i の原材料コスト C_i、製造に必要な時間 T_i、売値 P_i が、空白区切りで与えられる。

出力

得られる利益の合計の最大値を 1 行で出力せよ。

入力例 1

3 2 10
3 4 10
2 3 8
5 6 12

出力例 1

38

入力例 2

2 3 5
10 2 8
7 5 6

出力例 2

0

入力例 3

8 100 1000
120 50 260
200 80 390
90 30 150
300 120 500
500 200 850
40 25 70
1000 500 1600
250 70 410

出力例 3

280000

入力例 4

25 123456789 200000
100000 1 100500
200000 7 203000
300000 13 306500
400000 29 414000
500000 100 560000
600000 256 720000
700000 999 1000000
150000 1234 260000
250000 4096 450000
350000 8192 690000
450000 15000 900000
550000 20000 950000
650000 30000 980000
750000 50000 990000
800000 75000 1000000
900000 100000 1000000
100000 11111 180000
200000 22222 350000
300000 33333 520000
400000 44444 710000
500000 55555 830000
600000 66666 920000
700000 77777 970000
800000 88888 990000
900000 199999 1000000

出力例 4

14814814680000000

入力例 5

1 1 1
1 1 1

出力例 5

0

Score : 366 pts

Problem Statement

Takahashi runs a factory and earns profit by manufacturing and selling N types of products.

The factory has M manufacturing machines. Each machine has an available operating time of K minutes, and the total manufacturing time of products produced on each machine must not exceed K minutes.

For each product i (1 \leq i \leq N), the following information is given:

  • C_i: The raw material cost to manufacture one unit of product i (yen)
  • T_i: The time required to manufacture one unit of product i (minutes)
  • P_i: The selling price of one unit of product i (yen)

Manufacturing and selling one unit of product i yields a profit of P_i - C_i yen (if this value is negative, it represents a loss).

Each machine can only manufacture one product at a time, and manufacturing of a product cannot be interrupted midway. Once the manufacturing of one product is completed, the next product can be started immediately without any switching time.

The M machines operate independently of each other. There are sufficient raw materials, and any type of product can be manufactured without an upper limit on quantity. The types and quantities of products manufactured on each machine can be freely chosen for each machine, and the same type of product can be manufactured on multiple machines.

It is also permitted for a machine to manufacture no products at all. The profit from a machine that manufactures no products is 0 yen.

Find the maximum total profit that can be obtained from all M machines.

Constraints

  • 1 \leq N \leq 500
  • 1 \leq M \leq 10^9
  • 1 \leq K \leq 200{,}000
  • 1 \leq C_i \leq 10^6 (1 \leq i \leq N)
  • 1 \leq T_i \leq K (1 \leq i \leq N)
  • 1 \leq P_i \leq 10^6 (1 \leq i \leq N)
  • All inputs are integers.
  • It is guaranteed that the answer does not exceed 2^{63} - 1 (= 9{,}223{,}372{,}036{,}854{,}775{,}807, the maximum value of a 64-bit signed integer).

Input

N M K
C_1 T_1 P_1
C_2 T_2 P_2
\vdots
C_N T_N P_N
  • The first line contains the number of product types N, the number of machines M, and the available operating time per machine (in minutes) K, separated by spaces.
  • In the following N lines, the i-th line (1 \leq i \leq N) contains the raw material cost C_i, the manufacturing time T_i, and the selling price P_i of product i, separated by spaces.

Output

Output the maximum total profit that can be obtained in a single line.

Sample Input 1

3 2 10
3 4 10
2 3 8
5 6 12

Sample Output 1

38

Sample Input 2

2 3 5
10 2 8
7 5 6

Sample Output 2

0

Sample Input 3

8 100 1000
120 50 260
200 80 390
90 30 150
300 120 500
500 200 850
40 25 70
1000 500 1600
250 70 410

Sample Output 3

280000

Sample Input 4

25 123456789 200000
100000 1 100500
200000 7 203000
300000 13 306500
400000 29 414000
500000 100 560000
600000 256 720000
700000 999 1000000
150000 1234 260000
250000 4096 450000
350000 8192 690000
450000 15000 900000
550000 20000 950000
650000 30000 980000
750000 50000 990000
800000 75000 1000000
900000 100000 1000000
100000 11111 180000
200000 22222 350000
300000 33333 520000
400000 44444 710000
500000 55555 830000
600000 66666 920000
700000 77777 970000
800000 88888 990000
900000 199999 1000000

Sample Output 4

14814814680000000

Sample Input 5

1 1 1
1 1 1

Sample Output 5

0