AT_past18_m グループ分け

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.

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 $

Print the answer.

### Sample Explanation 1 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 Explanation 2 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 $ . ### 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.