Oland must not fall

Interview

Time limit2sMemory limit512 MB

Summary

Given hospital supplies, demands, and an undirected tunnel graph with unit edge costs, find the minimum total cost to balance every hospital, or -1 if impossible.

Level: Medium6 of 10
Topics: Graph, BFS, Greedy, Implementation
Solved: No attempts yet

Problem

A month has passed since the sixth army of the evil Miniophers invaded Olandica. Their troops are spread across Oland, a strategic city in western Olandica, and civilian casualties are heavy. The Olanders still hold a few hospitals, but they are short of Unophine, the drug that treats the damage caused by a biological weapon the Miniophers use. In response the Olanders dug a number of tunnels between hospitals. A pack of Unophine can be carried from one hospital to another whenever a tunnel joins them. The tunnels are narrow, so only one pack passes at a time, but the same tunnel can be used again as many times as needed.

Three times a day every hospital reports to the operations HQ how many packs it stores and how many packs it needs. HQ then builds a distribution plan that leaves every hospital holding exactly the number of packs it needs. The cost of a plan counts each pack once for every tunnel it crosses. A pack that crosses two tunnels costs $2$ .

For example, suppose hospitals A, B, and C store $3$ , $2$ , and $3$ packs, with a tunnel between A and B and a tunnel between B and C. If they need $4$ , $3$ , and $1$ packs, moving one pack from B to A and two packs from C to B works. That plan costs $3$ .

Given the tunnels and each hospital's storage and need, find the minimum cost of a distribution plan that leaves every hospital holding exactly what it needs.

Input

The first line contains the number of test cases $T$ ( $1 \le T \le 31$ ).

The first line of each test case contains the number of hospitals $L$ and the number of tunnels $R$ ( $1 \le L, R \le 128$ ). Hospitals are numbered from $1$ to $L$ .

Each of the next $L$ lines contains two integers $s_i$ and $n_i$ , the number of packs hospital $i$ stores and the number of packs it needs ( $0 \le s_i, n_i \le 10000$ ).

Each of the next $R$ lines contains two integers $i$ and $j$ , meaning that a tunnel joins hospital $i$ and hospital $j$ ( $1 \le i, j \le L$ ). Several tunnels may join the same pair of hospitals, and $i$ may equal $j$ .

Output

For each test case, print the minimum cost of a distribution plan on one line. If no plan leaves every hospital holding exactly what it needs, print $-1$ .

Examples3

Example 1

Input

Expected output

2
-1

Example 2
Input
```
1
3 2
3 4
2 3
3 1
1 2
2 3
```
Expected output
```
3
```
Example 3
Input
```
1
4 3
1 0
0 1
1 0
0 1
1 2
2 3
3 4
```
Expected output
```
2
```