Problem Statement

Given is a simple undirected graph with $N$ vertices and $M$ edges. Its vertices are numbered $1,2,\dots ,N$ and its edges are numbered $1,2,\dots ,M$. On Vertex $i$ ($1\le i\le N$) two integers Ai​ and Bi​ are written. Edge $i$ ($1\le i\le M$) connects Vertices Ui​ and Vi​.

Snuke picks zero or more vertices and delete them. Deleting Vertex $i$ costs Ai​. When a vertex is deleted, edges that are incident to the vertex are also deleted. The score after deleting vertices is calculated as follows:

• The score is the sum of the scores of all connected components.
• The score of a connected component is the absolute value of the sum of Bi​ of the vertices in the connected component.

Snuke's profit is $($score$)$ $-$ $($the sum of costs$)$. Find the maximum possible profit Snuke can gain.

Constraints

• $1\le N\le 300$
• $1\le M\le 300$
• 1≤Ai​≤106
• −106≤Bi​≤106
• 1≤Ui​,Vi​≤N
• The given graph does not contain self loops or multiple edges.
• All values in input are integers.

Sample Input 1

4 4
4 1 2 3
0 2 -3 1
1 2
2 3
3 4
4 2

Sample Output 1

1

Deleting Vertex $2$ costs $1$. After that, the graph is separated into two connected components. The score of the component consisting of Vertex $1$ is $|0|=0$. The score of the component consisting of Vertices $3$ and $4$ is $|(-3)+1|=2$. Therefore, Snuke's profit is $0+2-1=1$. He cannot gain more than $1$, so the answer is $1$.

Sample Input 2

10 12
733454 729489 956011 464983 822120 364691 271012 762026 751760 965431
-817837 -880667 -822819 -131079 740891 581865 -191711 -383018 273044 476880
3 1
4 1
6 9
3 8
1 6
10 5
5 6
1 5
4 3
7 1
7 4
10 3

Sample Output 2

2306209

Sample Input 3

4 2
1 1 1 1
1 1 -1 -1
1 2
3 4

Sample Output 3

4

The given graph is not necessarily connected.