올란드가 무너져서는 안 된다

사악한 미니오퍼 제6군이 올란디카를 침공한 지 한 달이 지났다. 미니오퍼 병력은 올란디카 서부의 요충지 올란드 전역에 퍼져 있고, 민간인 피해가 크다. 올란드 사람들은 아직 병원 몇 곳을 지키고 있지만, 미니오퍼가 쓰는 생물 무기의 피해를 치료하는 약 우노핀이 모자란다. 그래서 올란드 사람들은 병원 사이를 잇는 땅굴을 여러 개 팠다. 땅굴로 이어진 두 병원 사이에서는 우노핀 팩을 옮길 수 있다. 땅굴이 좁아서 한 번에 한 팩씩만 지나가지만, 같은 땅굴은 몇 번이든 다시 쓸 수 있다.

하루 세 번, 각 병원은 작전 본부에 지금 보관 중인 팩 수와 필요한 팩 수를 알린다. 본부는 모든 병원의 보유량을 필요량과 정확히 일치시키는 분배 계획을 세운다. 계획의 비용은 땅굴을 지나간 팩을 모두 센 값이다. 한 팩이 땅굴 두 개를 거쳐 가면 비용은 $2$다.

예를 들어 병원 A, B, C가 각각 $3$, $2$, $3$팩을 보관하고 있고 A와 B 사이, B와 C 사이에 땅굴이 있다고 하자. 필요량이 각각 $4$, $3$, $1$팩이라면 B에서 A로 한 팩을 옮기고 C에서 B로 두 팩을 옮기면 된다. 이 계획의 비용은 $3$이다.

땅굴과 각 병원의 보관량, 필요량이 주어질 때 모든 병원의 보유량을 필요량과 일치시키는 분배 계획의 최소 비용을 구하라.

첫 줄에 테스트 케이스의 수 $T$가 주어진다 ($1 \le T \le 31$).

각 테스트 케이스의 첫 줄에는 병원의 수 $L$과 땅굴의 수 $R$이 주어진다 ($1 \le L, R \le 128$). 병원에는 $1$번부터 $L$번까지 번호가 붙어 있다.

다음 $L$개 줄 중 $i$번째 줄에는 $i$번 병원이 보관 중인 팩 수 $s_i$와 필요한 팩 수 $n_i$가 주어진다 ($0 \le s_i, n_i \le 10000$).

다음 $R$개 줄에는 각각 두 정수 $i$와 $j$가 주어지며, $i$번 병원과 $j$번 병원을 잇는 땅굴이 있다는 뜻이다 ($1 \le i, j \le L$). 같은 두 병원을 잇는 땅굴이 여러 개일 수 있고, $i$와 $j$가 같을 수도 있다.

각 테스트 케이스마다 분배 계획의 최소 비용을 한 줄에 출력한다. 모든 병원의 보유량을 필요량과 일치시키는 계획이 없으면 $-1$을 출력한다.