Combined Purchase

Problem Background

Special for beginners, ^_^

Problem Description

Joe thinks clouds are beautiful, so he decides to go to the mountain shop to buy some clouds. The shop has $n$ clouds, numbered $1, 2, \dots, n$, and each cloud has a value. But the shopkeeper tells him that some clouds must be bought together to be worthwhile, so buying one cloud also requires buying all the clouds matched with it.

However, Joe has limited money, so he wants to get as much value as possible.

Input Format

The first line contains $n, m, w$, meaning $n$ clouds, $m$ matches, and Joe has $w$ money.

Lines $2$ to $n+1$: each line contains $c_i, d_i$, the price and the value of the $i$-th cloud.

Lines $n+2$ to $n+1+m$: each line contains $u_i, v_i$, meaning buying $u_i$ requires buying $v_i$, and similarly buying $v_i$ requires buying $u_i$.

Output Format

One line: the maximum value obtainable.

Sample Input

5 3 10
3 10
3 10
3 10
5 100
10 1
1 3
3 2
4 2

Sample Output

1

Constraints

Time limit: 1s; memory limit: 1024 KiB for each test case.

For $30\%$ of the data: $n \le 100$.

For $50\%$ of the data: $n \le 1000$, $m \le 100$, $w \le 1000$.

For $100\%$ of the data: $n \le 10000$, $0 \le m \le 5000$, $w \le 10000$.