AT_past18_m グループ分け

有 $N$ 个人，编号为 $1$ 到 $N$。第 $i$ 个人有 $A_i$ 颗糖果。 此外，给定 $M$ 组关系，每组 $(X_1, Y_1),\ldots,(X_M, Y_M)$ 表示这两个人关系不好。 请你将 $N$ 个人划分到若干个组内，使得满足以下两个条件时，所需组数最少： - 每个组内所有人的糖果总数不超过 $S$。 - 任意关系不好的一对人，不能在同一个组内。

输入从标准输入读入，格式如下： > $N$ $M$ $S$ $A_1$ $A_2$ $\ldots$ $A_N$ $X_1$ $Y_1$ $X_2$ $Y_2$ $\vdots$ $X_M$ $Y_M$

输出最小的满足条件的分组数。

### 样例解释 1 第 $1$ 个人与第 $2$ 个人关系不好，因此不能在同一组。我们可以将他们分成两个组，一个组只有第 $1$ 个人，另一个组有第 $2$ 和第 $3$ 个人，这样满足条件。 ### 样例解释 2 可以分为三个组：一个组有 $1, 2, 3$ 号，另一个组只有 $4$ 号，最后一个组只有 $5$ 号，也可以满足要求。 ### 数据范围 - $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$ - 所有输入均为整数。 由 ChatGPT 5 翻译