D - Team Building Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 366 点

問題文

高橋君は、会社のプロジェクトチームを編成する担当者です。

社内には N 人の社員がおり、各社員には 1 から N までの社員番号が付けられています。社員 i の能力値は A_i です。

高橋君は、N 人の中からちょうど K 人の社員を選んでチームを編成することにしました。同じ社員を複数回選ぶことはできず、各社員はチームに選ばれるか選ばれないかのいずれかです。

ただし、社員同士には相性の問題がある場合があります。M 組の「相性の悪いペア」が与えられ、j 番目のペアは社員 U_j と社員 V_j からなります。この 2 人がともにチームに選ばれている場合、連携がうまくいかず、チームの総合力が B_j だけ減少してしまいます。ペアのうち片方のみが選ばれている場合や、どちらも選ばれていない場合には減少は発生しません。

具体的には、選ばれた K 人の社員番号の集合を S（S \subseteq \{1, 2, \ldots, N\}, |S| = K）とするとき、チームの総合力は次のように定義されます。

\sum_{i \in S} A_i \ - \sum_{\substack{1 \leq j \leq M \\ U_j \in S \text{ かつ } V_j \in S}} B_j

すなわち、選ばれた K 人の能力値の合計から、両者がともに S に含まれるすべての相性の悪いペアによる減少分の合計を引いた値です。

高橋君がチームの総合力を最大化するように K 人を選ぶとき、チームの総合力の最大値を求めてください。なお、総合力は負になることもありますが、その場合でも最大値をそのまま出力してください。

制約

  • 1 \leq N \leq 18
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9
  • 1 \leq U_j < V_j \leq N
  • 1 \leq B_j \leq 10^9
  • (U_j, V_j) はすべて相異なる
  • 入力はすべて整数

入力

N M K
A_1 A_2 \ldots A_N
U_1 V_1 B_1
U_2 V_2 B_2
\vdots
U_M V_M B_M
  • 1 行目には、社員の数 N 、相性の悪いペアの数 M 、チームに選ぶ社員の数 K が、スペース区切りで与えられる。
  • 2 行目には、各社員の能力値 A_1, A_2, \ldots, A_N が、スペース区切りで与えられる。
  • 続く M 行（3 行目から M + 2 行目）には、相性の悪いペアの情報が与えられる。M = 0 の場合、この部分は存在しない。
  • 2 + j 行目では、j 番目の相性の悪いペアを構成する社員の番号 U_j と V_j 、およびチーム総合力の減少量 B_j が、スペース区切りで与えられる。

出力

チームの総合力の最大値を 1 行で出力してください。

入力例 1

4 2 2
10 8 6 5
1 2 3
3 4 2

出力例 1

16

入力例 2

5 4 3
100 90 80 70 60
1 2 50
1 3 40
2 3 30
4 5 10

出力例 2

220

入力例 3

8 6 4
1000000000 900000000 800000000 700000000 600000000 500000000 400000000 300000000
1 2 500000000
1 3 400000000
2 3 300000000
1 4 200000000
5 6 100000000
7 8 50000000

出力例 3

2700000000

Score : 366 pts

Problem Statement

Takahashi is in charge of forming a project team at his company.

There are N employees in the company, each assigned an employee number from 1 to N. The ability value of employee i is A_i.

Takahashi has decided to select exactly K employees from the N employees to form a team. The same employee cannot be selected more than once, and each employee is either selected for the team or not.

However, there may be compatibility issues between some employees. M "incompatible pairs" are given, where the j-th pair consists of employee U_j and employee V_j. If both of these employees are selected for the team, their coordination suffers and the team's overall strength decreases by B_j. If only one of the pair is selected, or neither is selected, no decrease occurs.

Specifically, let S (S \subseteq \{1, 2, \ldots, N\}, |S| = K) be the set of employee numbers of the K selected employees. The team's overall strength is defined as follows:

\sum_{i \in S} A_i \ - \sum_{\substack{1 \leq j \leq M \\ U_j \in S \text{ and } V_j \in S}} B_j

That is, it is the total ability values of the K selected employees minus the total decrease from all incompatible pairs where both members are included in S.

When Takahashi selects K employees to maximize the team's overall strength, find the maximum value of the team's overall strength. Note that the overall strength may be negative, but even in that case, output the maximum value as is.

Constraints

  • 1 \leq N \leq 18
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1 \leq K \leq N
  • 1 \leq A_i \leq 10^9
  • 1 \leq U_j < V_j \leq N
  • 1 \leq B_j \leq 10^9
  • All (U_j, V_j) are distinct
  • All input values are integers

Input

N M K
A_1 A_2 \ldots A_N
U_1 V_1 B_1
U_2 V_2 B_2
\vdots
U_M V_M B_M
  • The first line contains the number of employees N, the number of incompatible pairs M, and the number of employees to select for the team K, separated by spaces.
  • The second line contains the ability values of each employee A_1, A_2, \ldots, A_N, separated by spaces.
  • The following M lines (from the 3rd line to the (M + 2)-th line) contain the information about the incompatible pairs. If M = 0, this part does not exist.
  • The (2 + j)-th line contains the employee numbers U_j and V_j forming the j-th incompatible pair, and the decrease in overall strength B_j, separated by spaces.

Output

Output the maximum value of the team's overall strength in a single line.

Sample Input 1

4 2 2
10 8 6 5
1 2 3
3 4 2

Sample Output 1

16

Sample Input 2

5 4 3
100 90 80 70 60
1 2 50
1 3 40
2 3 30
4 5 10

Sample Output 2

220

Sample Input 3

8 6 4
1000000000 900000000 800000000 700000000 600000000 500000000 400000000 300000000
1 2 500000000
1 3 400000000
2 3 300000000
1 4 200000000
5 6 100000000
7 8 50000000

Sample Output 3

2700000000