← 返回题目列表

AtCoder · past18_m

M. 分组

中文机器翻译题面 查看原题

问题陈述

有 N 人数 1 to N。人 i 有 A_i 糖果。

此外,您还获得 M 对人 (X_1,Y_1),\ldots,(X_M,Y_M) 彼此关系不好。

最少可分为多少组 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

5 0 10
2 3 4 10 10

示例输出 2

3

通过将其分为三组来满足条件:一组由人组成 1,2,3,仅由人组成 4,并且一个仅由人组成 5.


示例输入 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