题目描述

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

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

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

输入格式

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

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

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

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

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

输出格式

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

样例

输入样例

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

输出样例

110

提示

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