E - Exhibition Booth Planning Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 433 点

問題文

高橋君は展示会の出展プランナーをしています。倉庫には N 個の展示品があり、展示品 i（1 \leq i \leq N）には 重さ w_i、見込み利益 v_i、および 出展先の会場番号 d_i が決まっています。会場番号は 1 から K までの整数です。

高橋君は輸送用のトラックを 1 台持っており、トラックの積載量は W です。高橋君はこれらの展示品の中からいくつかを選んでトラックに積み込み、選んだ展示品をそれぞれの出展先の会場に届けます。各展示品は積むか積まないかのいずれかであり、同じ展示品を複数回選ぶことはできません。また、1 個も選ばないことも可能です。トラックに積む展示品の重さの合計は W 以下でなければなりません。

選んだ展示品を届けるにあたって、配送コストが発生します。トラックに積んだ展示品の出展先に含まれる 異なる会場の数 を c とすると、配送コストは c^2 です。同じ会場宛の展示品が複数あっても、その会場は 1 つと数えます。1 個も展示品を選ばない場合は c = 0 です。

一方、選んだ展示品 i を届けることで見込み利益 v_i が得られます。

高橋君は、トラックに積む展示品の集合を適切に選んで、

\text{（選んだ展示品の見込み利益の合計）} - \text{（配送コスト）}

を最大化したいと考えています。この最大値を求めてください。

なお、1 個も選ばない場合は見込み利益の合計も配送コストもともに 0 となるため、上の式の値は 0 になります。したがって、答えは必ず 0 以上です。

制約

  • 1 \leq N \leq 300
  • 1 \leq K \leq 8
  • 1 \leq W \leq 3000
  • 1 \leq w_i \leq W (1 \leq i \leq N)
  • 1 \leq v_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq d_i \leq K (1 \leq i \leq N)
  • 入力はすべて整数である。

入力

N K W
w_1 v_1 d_1
w_2 v_2 d_2
\vdots
w_N v_N d_N
  • 1 行目には、展示品の数 N、会場の数 K、トラックの積載量 W が、スペース区切りで与えられる。
  • 2 行目から N + 1 行目では、各展示品の情報が 1 行ずつ与えられる。
  • 1 + i 行目（1 \leq i \leq N）には、展示品 i の重さ w_i、見込み利益 v_i、出展先の会場番号 d_i が、スペース区切りで与えられる。

出力

（選んだ展示品の見込み利益の合計）-（配送コスト）の最大値を 1 行で出力せよ。

入力例 1

4 3 7
3 8 1
4 7 1
2 4 2
5 10 3

出力例 1

14

入力例 2

3 2 2
2 1 1
2 1 2
1 1 2

出力例 2

0

入力例 3

12 5 25
4 9 1
7 13 2
3 8 1
6 12 3
5 7 2
8 20 4
2 5 5
9 18 3
1 3 4
10 25 5
4 11 2
6 14 1

出力例 3

57

入力例 4

30 8 120
12 40 1
15 55 2
7 20 1
22 80 3
18 60 4
9 25 5
30 120 6
11 35 7
14 45 8
26 95 2
5 18 3
33 150 4
16 70 1
21 85 5
8 28 6
12 48 7
19 77 8
27 110 3
6 22 4
24 90 2
10 36 5
31 130 6
17 65 7
13 52 8
28 115 1
20 82 4
4 15 2
25 100 5
29 125 6
23 88 3

出力例 4

506

入力例 5

1 1 1
1 1 1

出力例 5

0

Score : 433 pts

Problem Statement

Takahashi is an exhibition planner. There are N exhibit items in the warehouse, and for each exhibit item i (1 \leq i \leq N), a weight w_i, an expected profit v_i, and a destination venue number d_i are determined. Venue numbers are integers from 1 to K.

Takahashi has one truck for transportation, with a loading capacity of W. Takahashi selects some of these exhibit items, loads them onto the truck, and delivers each selected item to its respective destination venue. Each item is either loaded or not loaded; the same item cannot be selected multiple times. It is also possible to select no items at all. The total weight of the items loaded onto the truck must not exceed W.

A delivery cost is incurred when delivering the selected items. Let c be the number of distinct venues among the destinations of the items loaded onto the truck. The delivery cost is c^2. Even if there are multiple items destined for the same venue, that venue is counted only once. If no items are selected, then c = 0.

On the other hand, delivering a selected exhibit item i yields an expected profit of v_i.

Takahashi wants to appropriately choose the set of items to load onto the truck to maximize:

\text{(total expected profit of selected items)} - \text{(delivery cost)}

Find this maximum value.

Note that if no items are selected, both the total expected profit and the delivery cost are 0, so the value of the above expression is 0. Therefore, the answer is always at least 0.

Constraints

  • 1 \leq N \leq 300
  • 1 \leq K \leq 8
  • 1 \leq W \leq 3000
  • 1 \leq w_i \leq W (1 \leq i \leq N)
  • 1 \leq v_i \leq 10^4 (1 \leq i \leq N)
  • 1 \leq d_i \leq K (1 \leq i \leq N)
  • All inputs are integers.

Input

N K W
w_1 v_1 d_1
w_2 v_2 d_2
\vdots
w_N v_N d_N
  • The first line contains the number of exhibit items N, the number of venues K, and the truck's loading capacity W, separated by spaces.
  • From the 2nd line to the (N + 1)-th line, the information of each exhibit item is given, one per line.
  • The (1 + i)-th line (1 \leq i \leq N) contains the weight w_i, expected profit v_i, and destination venue number d_i of exhibit item i, separated by spaces.

Output

Output the maximum value of (total expected profit of selected items) - (delivery cost) in a single line.

Sample Input 1

4 3 7
3 8 1
4 7 1
2 4 2
5 10 3

Sample Output 1

14

Sample Input 2

3 2 2
2 1 1
2 1 2
1 1 2

Sample Output 2

0

Sample Input 3

12 5 25
4 9 1
7 13 2
3 8 1
6 12 3
5 7 2
8 20 4
2 5 5
9 18 3
1 3 4
10 25 5
4 11 2
6 14 1

Sample Output 3

57

Sample Input 4

30 8 120
12 40 1
15 55 2
7 20 1
22 80 3
18 60 4
9 25 5
30 120 6
11 35 7
14 45 8
26 95 2
5 18 3
33 150 4
16 70 1
21 85 5
8 28 6
12 48 7
19 77 8
27 110 3
6 22 4
24 90 2
10 36 5
31 130 6
17 65 7
13 52 8
28 115 1
20 82 4
4 15 2
25 100 5
29 125 6
23 88 3

Sample Output 4

506

Sample Input 5

1 1 1
1 1 1

Sample Output 5

0