问题陈述
有 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