题目背景

这本是一个非常简单的问题，然而奶牛们由于下雨已经非常混乱，无法完成这一计算，于是这个任务就交给了你。(奶牛混乱的原因看题目描述)

题目描述

在一个农场里有 $n$ 块田地。某天下午，有一群牛在田地里吃草，他们分散在农场的诸多田地上，农场由 $m$ 条无向的路连接，每条路有不同的长度。

突然，天降大雨，奶牛们非常混乱，想要快点去躲雨。已知每个田地都建立有一个牛棚，但是每个牛棚只能容纳一定数量的牛躲雨，如果超过这个数量，那多出的牛只能去别的田地躲雨。奶牛们每移动 $1$ 的距离花费 $1$ 时间，奶牛们想知道它们全部都躲进牛棚，最少需要多少时间。(即最后一头奶牛最少要花多久才能躲进牛棚)。

输入格式

第一行有两个整数，分别代表田地数 $n$ 和道路数 $m$。

接下来 $n$ 行，每行两个整数，第 $(i + 1)$ 行的整数 $s_i, p_i$ 分别表示第 $i$ 块田地的牛的数量以及该田地的牛棚最多可以容纳多少牛。

接下来 $m$ 行，每行三个整数 $u, v, w$，代表存在一条长度为 $w$ 的连接 $u$ 和 $v$ 的道路。

输出格式

输出一行一个整数表示所有奶牛全都躲进牛棚所用的最少时间。如果无法使全部奶牛都躲进牛棚，输出 $-1$。

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

110

提示

样例输入输出 1 解释

$1$ 号点的两只牛直接躲进 $1$ 号牛棚，剩下的 $5$ 只中，$4$ 只跑去 $2$ 号点，还有一只沿 $1 \to 2 \to 3$ 躲进 $3$ 号点, $3$ 号点的 $2$ 只牛也直接躲进去，这样最慢的牛花费的时间是 $110$。

数据规模与约定

对于 $100\%$ 的数据，保证：

• $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}$。