Description

Joe finds the clouds beautiful and decides to buy some from a shop on the mountain. There are n clouds in the shop, numbered from 1 to n, and each cloud has a certain value. However, the shop owner tells him that some clouds are meant to be bought together, so purchasing one cloud means he must also buy all the clouds that are paired with it.

But Joe has limited money, so he wants to maximize the total value of the clouds he can buy.

Input Format

• The first line contains three integers: n, m, and w, representing the number of clouds, the number of pairings, and the amount of money Joe has.
• The next n lines (lines 2 to n+1) each contain two integers, ci and di, representing the cost and value of the i-th cloud.
• The following m lines (lines n+2 to n+1+m) each contain two integers, ui and vi, indicating that buying cloud ui requires buying cloud vi, and vice versa.

Output Format

A single line representing the maximum value Joe can obtain.

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

1

Hint

【Data Range】 For 30% of the data, it is guaranteed that: n ≤ 100
For 50% of the data, it is guaranteed that: n ≤ 1,000; m ≤ 100; w ≤ 1,000
For 100% of the data, it is guaranteed that: n ≤ 10,000; 0 ≤ m ≤ 5,000; w ≤ 10,000