题目描述

约翰的牛们非常害怕淋雨，那会使他们瑟瑟发抖．他们打算安装一个下雨报警器，并且安排了一个撤退计划．他们需要计算最少的让所有牛进入雨棚的时间．

牛们在农场的$\red{F(1≤}$$\red{F≤}$$\red{200)}$个田地上吃草．有$\red{P(1≤}$$\red{P≤}$$\red{1500)}$条双向路连接着这些田地．路很宽，无限量的牛可以通过．田地上有雨棚，雨棚有一定的容量，牛们可以瞬间从这块田地进入这块田地上的雨棚

请计算最少的时间，让每只牛都进入雨棚．

输入格式

第$\red{1}$行：两个整数$\red{F}$和$\red{P}$;

第$\red{2}$到$\red{F+1}$行：

第$\red{i+l}$行有两个整数描述第$\red{i}$个田地，第一个表示田地上的牛数，第二个表示田地上的雨棚容量．两个整数都在$\red{0}$和$\red{1000}$之间．

第$\red{F+2}$到$\red{F+P+I}$行：

每行三个整数描述一条路，分别是起点终点，及通过这条路所需的时间（在$\red{1}$和$\red{10^9}$之间）．

输出格式

一个整数，表示最少的时间．如果无法使牛们全部进入雨棚，输出$\red{-1.}$

样例

输入样例

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

输出样例

110

提示

$\red{1}$号田的$\red{7}$只牛中，$\red{2}$只牛直接进入$\red{1}$号田的雨棚，$\red{4}$只牛进入$\red{1}$号田的雨棚，$\red{1}$只进入$\red{3}$号田的雨棚，加入其他的由$\red{3}$号田来的牛们．所有的牛都能在$\red{110}$单位时间内到达要去的雨棚．