The Great Tea Party

Limits: 2 sec., 256 MiB

When Lesyk, Roman and Vitalik happen to get bored drinking tea alone they invite tea funs to the great tea party.

The guys know N tea funs. If the i-th fun is invited he or she will bring \(\mathbf{A_i}\) liters of tea to the party and will drink \(\mathbf{B_i}\) liters of tea at the party.

Also there are friendship relations between some pairs of the tea funs. If two funs are friends and you want to invite one of them to the party you would have to invite other friend as well (since it won’t be polite to invite only one of them).

When the party is over the organizers will drink the tea which is left. Obviously they would like to maximize this amount. Would you please help them to find it?

Input

The first line contains two integers N and M. Here M is the number of friendship relations between tea funs. Each of the following N lines contains two integers \(\mathbf{A_i}\) and \(\mathbf{B_i}\).

Each of the following M lines contains two integers \(\mathbf{X_i}\) and \(\mathbf{Y_i}\). For each valid \(i\) fun \(\mathbf{X_i}\) and fun \(\mathbf{Y_i}\) are friends (funs are numbered from 1 to N).

Output

The maximal possible amount of tea that could be left after the party.

Constraints

\(1 \le \mathbf{N} \le 100\),

\(1 \le \mathbf{M} \le 10000\),

\(0 \le \mathbf{A_i}, \mathbf{B_i} \le 1000\),

\(1 \le \mathbf{X_i}, \mathbf{Y_i} \le N\).

Samples

Input (stdin) сopy	Output (stdout) сopy
3 1 10 3 2 10 7 6 1 2	1

Notes

It makes sense to invite only fun 3. If you invite fun 1 then fun 2 has to be invited as well.