Description

FJ’s cows are very afraid of getting rained on, which makes them shiver. They plan to install a rain alarm and arrange an evacuation plan. They need to compute the minimum time needed to get all cows into shelters.

The cows graze on $F$ fields on the farm. There are $P$ bidirectional roads connecting these fields. The roads are wide, so an unlimited number of cows can pass through them. Each field has a shelter with a certain capacity, and cows can enter the shelter on the same field instantly.

Compute the minimum time so that every cow can enter a shelter.

Input Format

Line $1$: two integers $F$ and $P$.
Lines $2$ to $F+1$: on line $i+1$, there are two integers describing field $i$. The first is the number of cows on the field, and the second is the shelter capacity on that field. Both integers are between $0$ and $1000$.
Lines $F+2$ to $F+P+1$: each line contains three integers describing a road: the two endpoints, and the time needed to travel along this road (between $1$ and $10^9$).

Output Format

One integer, the minimum time. If it is impossible to get all cows into shelters, output $-1$.

3 4
7 2
0 4
2 6
1 2 40
3 2 70
2 3 90
1 3 120

110

Hint

Constraints: for $100\%$ of the testdata, $1 \le F \le 200$, $1 \le P \le 1500$.

Translated by ChatGPT 5