B - ナップサック問題 /

実行時間制限: 2 sec / メモリ制限: 1024 MB

配点 : 200

問題文

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)

入力

入力は以下の形式で標準入力から与えられる。

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

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