問題文

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 を超えないようにいくつか品物を選んだときの価値の総和の最大値を求めてください。

制約

• 入力中の値は全て整数である。
• 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)

入力例 1

3 1 10
3 2
5 4
3 3
1 2

出力例 1

6

1 番目の品物と 2 番目の品物を選ぶことで価値の総和を 6 にすることができ、これが最適です。

条件から、2 番目の品物と 3 番目の品物だけを選ぶことはできないことに注意してください。

入力例 2

4 0 10
1 1
2 2
3 3
4 4

出力例 2

10

全ての品物を選ぶことができます。

入力例 3

3 3 6
2 5
3 8
3 4
1 2
2 3
3 1

出力例 3

0

一つも品物を選ぶことができません。

入力例 4

1 0 10000
10000 10000000

出力例 4

10000000