Problem Description

There are $ n $ items, numbered from $ 1 $ to $ n $.

Each item has a value and a weight, where the value of the $ i $-th item is $ v_i $ and the weight is $ w_i $.

You want to select some of these items such that the total weight does not exceed $ W $, and maximize the total value of the selected items.

However, there are $ m $ conditions.

The $ j $-th condition is represented by $ (a_j, b_j) $, which means "If you select the $ a_j $-th item, you must also select the $ b_j $-th item, and if you select the $ b_j $-th item, you must also select the $ a_j $-th item."

Find the maximum total value of the items you can select from the $ n $ items without exceeding the total weight $ W $ while satisfying all the conditions.

Input Format

The input is given from the standard input in the following format:

$ 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 $

Output Format

Output the maximum total value of the items you can select from the $ n $ items without exceeding the total weight $ W $ while satisfying all the conditions.

Sample Input and Output

Sample Input #1

3 1 10
3 2
5 4
3 3
1 2

Sample Output #1

6

Sample Input #2

4 0 10
1 1
2 2
3 3
4 4

Sample Output #2

10

Sample Input #3

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

Sample Output #3

0

Sample Input #4

1 0 10000
10000 10000000

Sample Output #4

10000000

Notes/Hints

Constraints

• All values in the input are integers.
• $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$
• If $i \neq j$, then $(a_i, b_i) \neq (a_j, b_j)$ and $(a_i, b_i) \neq (b_j, a_j)$

Sample Explanation 1

By selecting the $ 1 $-st item and the $ 2 $-nd item, you can achieve a total value of $ 6 $, which is optimal. Note that you cannot select only the $ 2 $-nd and $ 3 $-rd items due to the condition.

Sample Explanation 2

You can select all items.

Sample Explanation 3

You cannot select any items.

见题面 Input 部分

见题面 Output 部分