AT_past18_m グループ分け

$ 1 $ から $ N $ の番号がついた $ N $ 人の人がいます。人 $ i $ は飴を $ A_i $ 個持っています。 また、仲が悪い人の組 $ M $ 個 $ (X_1,Y_1),\ldots,(X_M,Y_M) $ が与えられます。 以下の $ 2 $ つの条件をともに満たすように $ 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 $

答えを出力せよ。

### Sample Explanation 1 人 $ 1 $ と人 $ 2 $ は仲が悪いため同じグループに属することができません。 人 $ 1 $ のみからなるグループと、人 $ 2,3 $ からなるグループの $ 2 $ グループに分けることで条件を満たします。 ### Sample Explanation 2 人 $ 1,2,3 $ からなるグループ、人 $ 4 $ のみからなるグループ、人 $ 5 $ のみからなるグループの $ 3 $ グループに分けることで条件を満たします。 ### Constraints - $ 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 $ - 入力は全て整数である