M - Grouping Editorial /

Time Limit: 4 sec / Memory Limit: 1024 MB

問題文

1 から N の番号がついた N 人の人がいます。人 i は飴を A_i 個持っています。

また、仲が悪い人の組 M 個 (X_1,Y_1),\ldots,(X_M,Y_M) が与えられます。

以下の 2 つの条件をともに満たすように N 人をいくつかのグループに分けるとき、グループ数の最小値はいくつですか？

  • どのグループも、そのグループに属する人が持っている飴の個数の合計が S 以下
  • 仲が悪い人の組が同じグループに属さない

制約

  • 1 \leq N \leq 20
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1\leq X_i < Y_i \leq N
  • (X_i,Y_i) は相異なる
  • 0 \leq A_i \leq 10^7
  • \max_i A_i \leq S \leq 10^9
  • 入力は全て整数である

入力

入力は以下の形式で標準入力から与えられる。

N M S
A_1 A_2 \ldots A_N
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

出力

答えを出力せよ。

入力例 1

3 1 10
2 3 4
1 2

出力例 1

2

人 1 と人 2 は仲が悪いため同じグループに属することができません。 人 1 のみからなるグループと、人 2,3 からなるグループの 2 グループに分けることで条件を満たします。

入力例 2

5 0 10
2 3 4 10 10

出力例 2

3

人 1,2,3 からなるグループ、人 4 のみからなるグループ、人 5 のみからなるグループの 3 グループに分けることで条件を満たします。

入力例 3

19 10 13639949
6248137 1929297 1115672 3165903 771666 2658398 3460632 3239969 5759071 1396990 5625214 7940774 1755330 7704375 8252319 2891254 3580852 7211614 6847141
11 17
1 11
9 10
10 16
11 19
4 14
2 9
9 19
9 11
17 19

出力例 3

7

Problem Statement

There are N people numbered 1 to N. Person i has A_i candies.

Additionally, you are given M pairs of people (X_1,Y_1),\ldots,(X_M,Y_M) who are on bad terms with each other.

What is the minimum number of groups into which the N people can be divided so that both of the following conditions are satisfied?

  • The people in each group have at most S candies in total.
  • No two people on bad terms are in the same group.

Constraints

  • 1 \leq N \leq 20
  • 0 \leq M \leq \frac{N(N-1)}{2}
  • 1\leq X_i < Y_i \leq N
  • The pairs (X_i,Y_i) are distinct.
  • 0 \leq A_i \leq 10^7
  • \max_i A_i \leq S \leq 10^9
  • All inputs are integers.

Input

The input is given from Standard Input in the following format:

N M S
A_1 A_2 \ldots A_N
X_1 Y_1
X_2 Y_2
\vdots
X_M Y_M

Output

Print the answer.

Sample Input 1

3 1 10
2 3 4
1 2

Sample Output 1

2

Person 1 and person 2 are on bad terms and thus cannot be in the same group. The conditions are satisfied by dividing them into two groups, one composed only of person 1 and the other composed of persons 2 and 3.

Sample Input 2

5 0 10
2 3 4 10 10

Sample Output 2

3

The conditions are satisfied by dividing them into three groups: one composed of persons 1,2,3, one composed only of person 4, and one composed only of person 5.

Sample Input 3

19 10 13639949
6248137 1929297 1115672 3165903 771666 2658398 3460632 3239969 5759071 1396990 5625214 7940774 1755330 7704375 8252319 2891254 3580852 7211614 6847141
11 17
1 11
9 10
10 16
11 19
4 14
2 9
9 19
9 11
17 19

Sample Output 3

7