E - 倉庫の配置計画 解説 /

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

配点 : 433 点

問題文

高橋君は N 個の区画からなる工業団地の管理者です。各区画には 1 から N までの番号が付けられており、区画 i には最大 P_i トンの荷物を保管できる倉庫を建設できます。

ある日、工業団地に合計 M トン分の荷物の保管依頼がありました。高橋君は、後述する条件を満たしながら、できるだけ多くの荷物を保管したいと考えています。

工業団地には K 本の通路があり、i 本目の通路は区画 U_i と区画 V_i を直接つないでいます。通路で直接つながっている 2 つの区画に同時に倉庫を建設すると、搬入トラックの動線が干渉するため、そのような配置は 禁止 されています。通路で直接つながっていない 2 つの区画であれば、同時に倉庫を建設しても問題ありません。

具体的には、高橋君は以下の手順で荷物を保管します。

  1. 倉庫を建設する区画の集合 S を選ぶ（S は空集合でもよい）。ただし、S に含まれるどの 2 つの区画も通路で直接つながっていてはならない。
  2. S に含まれる各区画 i に対して、0 以上 P_i 以下の整数値の荷物量を割り当てる。S に含まれない区画には倉庫がないため、荷物量は 0 とする。
  3. すべての区画の荷物量の合計は M 以下でなければならない。

このとき、すべての区画の荷物量の合計としてあり得る最大値を求めてください。

制約

  • 1 \leq N \leq 40
  • 1 \leq M \leq 10^{15}
  • 0 \leq K \leq \frac{N(N-1)}{2}
  • 1 \leq P_i \leq 10^{12} (1 \leq i \leq N)
  • 1 \leq U_i < V_i \leq N (1 \leq i \leq K)
  • (U_i, V_i) \neq (U_j, V_j) (i \neq j)
  • 入力はすべて整数

入力

N M K
P_1 P_2 \ldots P_N
U_1 V_1
U_2 V_2
\vdots
U_K V_K
  • 1 行目には、区画の数を表す整数 N、保管量の上限を表す整数 M、通路の本数を表す整数 K が、スペース区切りで与えられる。
  • 2 行目には、各区画の最大保管量を表す整数 P_1, P_2, \ldots, P_N が、スペース区切りで与えられる。
  • 3 行目から K + 2 行目には、通路の情報が与えられる。
  • 2 + i 行目では、i 本目の通路が区画 U_i と区画 V_i を直接つないでいることを表す。

出力

高橋君が保管できる荷物量の合計の最大値を整数で 1 行に出力してください。

入力例 1

4 10 2
3 5 4 6
1 2
3 4

出力例 1

10

入力例 2

6 100 5
10 20 30 15 25 5
1 2
2 3
3 4
4 5
5 6

出力例 2

65

入力例 3

10 1500000000000 8
100000000000 200000000000 150000000000 300000000000 250000000000 50000000000 400000000000 180000000000 350000000000 120000000000
1 2
2 3
1 5
4 7
4 9
5 6
7 9
8 9

出力例 3

1150000000000

Score : 433 pts

Problem Statement

Takahashi is the manager of an industrial park consisting of N lots. Each lot is numbered from 1 to N, and a warehouse capable of storing up to P_i tons of goods can be built on lot i.

One day, a request was made to store a total of M tons of goods in the industrial park. Takahashi wants to store as many goods as possible while satisfying the conditions described below.

The industrial park has K corridors, where the i-th corridor directly connects lot U_i and lot V_i. Building warehouses simultaneously on two lots that are directly connected by a corridor is prohibited, as the routes of delivery trucks would interfere with each other. If two lots are not directly connected by a corridor, warehouses may be built on both of them simultaneously without any issues.

Specifically, Takahashi stores goods according to the following procedure:

  1. Choose a set S of lots on which to build warehouses (S may be empty). No two lots in S may be directly connected by a corridor.
  2. For each lot i in S, assign an integer amount of goods between 0 and P_i inclusive. Lots not in S have no warehouse, so their goods amount is 0.
  3. The total amount of goods across all lots must be at most M.

Find the maximum possible value of the total amount of goods across all lots.

Constraints

  • 1 \leq N \leq 40
  • 1 \leq M \leq 10^{15}
  • 0 \leq K \leq \frac{N(N-1)}{2}
  • 1 \leq P_i \leq 10^{12} (1 \leq i \leq N)
  • 1 \leq U_i < V_i \leq N (1 \leq i \leq K)
  • (U_i, V_i) \neq (U_j, V_j) (i \neq j)
  • All input values are integers

Input

N M K
P_1 P_2 \ldots P_N
U_1 V_1
U_2 V_2
\vdots
U_K V_K
  • The first line contains the integer N representing the number of lots, the integer M representing the upper limit on storage, and the integer K representing the number of corridors, separated by spaces.
  • The second line contains the integers P_1, P_2, \ldots, P_N representing the maximum storage capacity of each lot, separated by spaces.
  • From the 3rd line to the (K + 2)-th line, corridor information is given.
  • The (2 + i)-th line indicates that the i-th corridor directly connects lot U_i and lot V_i.

Output

Output the maximum total amount of goods that Takahashi can store, as a single integer on one line.

Sample Input 1

4 10 2
3 5 4 6
1 2
3 4

Sample Output 1

10

Sample Input 2

6 100 5
10 20 30 15 25 5
1 2
2 3
3 4
4 5
5 6

Sample Output 2

65

Sample Input 3

10 1500000000000 8
100000000000 200000000000 150000000000 300000000000 250000000000 50000000000 400000000000 180000000000 350000000000 120000000000
1 2
2 3
1 5
4 7
4 9
5 6
7 9
8 9

Sample Output 3

1150000000000