AT_kupc2019_b ナップサック問題

[problemUrl]: https://atcoder.jp/contests/kupc2019/tasks/kupc2019_b $ n $ 個の品物があり、$ 1 $ から $ n $ までの番号が付けられています。 各品物には価値と重さが定められていて、$ i $ 番目の品物の価値は $ v_i $、重さは $ w_i $ です。 あなたはこれらの品物から重さの総和が $ W $ を超えないようにいくつか選び、選んだ品物の価値の総和を最大化したいです。 ただし、$ m $ 個の条件があります。 $ j $ 番目の条件は $ (a_j,\ b_j) $ で表され、それぞれ「 $ a_j $ 番目の品物を選ぶならば $ b_j $ 番目の品物を選ばなければならず、$ b_j $ 番目の品物を選ぶならば $ a_j $ 番目の品物を選ばなければならない」 という意味です。 これらの条件を全て満たした上で、$ n $ 個の品物から重さの総和が $ W $ を超えないようにいくつか品物を選んだときの価値の総和の最大値を求めてください。

入力は以下の形式で標準入力から与えられる。 > $ n $ $ m $ $ W $ $ w_1 $ $ v_1 $ $ w_2 $ $ v_2 $ $ \vdots $ $ w_n $ $ v_n $ $ a_1 $ $ b_1 $ $ a_2 $ $ b_2 $ $ \vdots $ $ a_m $ $ b_m $

$ m $ 個の条件を全て満たした上で、$ n $ 個の品物から重さの総和が $ W $ を超えないようにいくつか品物を選んだときの価値の総和の最大値を出力せよ。

### 制約 - 入力中の値は全て整数である。 - $ 1\ \leq\ n\ \leq\ 100 $ - $ 0\ \leq\ m\ \leq\ \frac\ {n(n-1)}{2} $ - $ 1\ \leq\ W\ \leq\ 10^4 $ - $ 1\ \leq\ w_i\ \leq\ W $ - $ 1\ \leq\ v_i\ \leq\ 10^7 $ - $ 1\ \leq\ a_i,\ b_i\ \leq\ n $ - $ a_i\ \neq\ b_i $ - $ i\ \neq\ j $ ならば、$ (a_i,\ b_i)\ \neq\ (a_j,\ b_j) $ かつ $ (a_i,\ b_i)\ \neq\ (b_j,\ a_j) $ ### Sample Explanation 1 $ 1 $ 番目の品物と $ 2 $ 番目の品物を選ぶことで価値の総和を $ 6 $ にすることができ、これが最適です。 条件から、$ 2 $ 番目の品物と $ 3 $ 番目の品物だけを選ぶことはできないことに注意してください。 ### Sample Explanation 2 全ての品物を選ぶことができます。 ### Sample Explanation 3 一つも品物を選ぶことができません。