Description

There are $n$ fields on a farm. One afternoon, a herd of cows is grazing in the fields. They are spread across many fields of the farm, which are connected by $m$ undirected roads, each with a different length.

Suddenly, heavy rain falls. The cows are very confused and want to find shelter quickly. It is known that each field has a barn, but each barn can only hold a limited number of cows. If the number of cows exceeds this capacity, the extra cows must go to other fields to shelter. Moving a distance of $1$ costs time $1$. The cows want to know the minimum time needed for all of them to get into barns, i.e., the minimum time the last cow needs to get into a barn.

Input Format

• The first line contains two integers, the number of fields $n$ and the number of roads $m$.
• The next $n$ lines each contain two integers. On the $(i + 1)$-th line, the integers $s_i, p_i$ denote the number of cows in field $i$ and the maximum capacity of the barn at that field, respectively.
• The next $m$ lines each contain three integers $u, v, w$, indicating there is an undirected road of length $w$ connecting $u$ and $v$.

Output Format

Output a single integer, the minimum time required for all cows to get into barns. If it is impossible for all cows to find shelter, output $-1$.

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

110

Hint

Sample Input/Output 1 Explanation:

The two cows at node $1$ go directly into barn $1$. Among the remaining $5$ cows, $4$ run to node $2$, and one goes along $1 \to 2 \to 3$ to get into barn $3$. The $2$ cows at node $3$ also go directly into its barn. In this arrangement, the slowest cow spends time $110$.

Constraints:

For $100\%$ of the data, it is guaranteed that:

• $1 \leq n \leq 200$, $1 \leq m \leq 1500$.
• $1 \leq u, v \leq n$, $1 \leq w \leq 10^{15}$, $1 \leq s_i, p_i \leq 10^{16}$.

Translated by ChatGPT 5