Description

Mother's Day is tomorrow, and the kids in the computer club are racking their brains about what gift to give to express their feelings. They heard that a certain website sells clouds, so they decided to check out this magical product together. The store has $n$ clouds, labeled $1,2,3,...,n$, and each cloud has a value. However, the shop owner is a peculiar person: he will tell you that some clouds must be bought together as a bundle. In other words, if you buy one cloud, then all clouds paired with it must also be bought. You find this gift idea very novel, but your money is limited, so you want to use your budget to buy clouds with the maximum total value.

Input Format

• The first line contains three integers $n,m,w$, meaning there are $n$ clouds, $m$ bundling relations, and your current amount of money $w$.
• From the second line to line $n+1$, each line contains two integers $c_i,d_i$, representing the price and value of the $i$-th cloud.
• From line $n+2$ to line $n+1+m$, each line contains two integers $u_i,v_i$, meaning if you buy cloud $u_i$, you must also buy cloud $v_i$. Similarly, if you buy cloud $v_i$, you must also buy cloud $u_i$.

Output Format

Output one line: the maximum total value you can obtain.

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

1

Hint

Constraints:

• For $30\%$ of the testdata, $1 \le n \le 100$.
• For $50\%$ of the testdata, $1 \le n, w \le 10^3$, $1 \le m \le 100$.
• For $100\%$ of the testdata, $1 \le n, w \le 10^4$, $0 \le m \le 5 \times 10^3$.

Translated by ChatGPT 5