问题重述

FJ的奶牛非常讨厌被淋湿，以至于一想到被雨淋到就会让它们蹄子发抖。他们决定在农场安装一个雨警报器，以便在雨来临之前通知它们。他们打算制定一个疏散计划，使得所有的奶牛都能在雨开始前到达避难所。然而，天气预报并不总是准确的。为了最小化误报，他们希望在尽可能晚的时候才发出警报，同时仍然给所有奶牛足够的时间到达某个避难所。

农场有F（1 ≤ F ≤ 200）个田地，奶牛在这些田地上吃草。有P（1 ≤ P ≤ 1500）条路径连接这些田地。路径很宽，可以容纳任意数量的奶牛双向通行。

一些田地上有避难所，可以供奶牛躲避。这些避难所的容量有限，因此一个避难所可能无法容纳所有的奶牛。田地的面积相对于路径来说很小，奶牛在田地之间移动不需要时间。

计算在雨开始前必须发出警报的最短时间，以便所有的奶牛都能到达某个避难所。如果无法让所有奶牛都到达避难所，则输出-1。

输入格式

第一行：两个整数F和P。

接下来的F行：每行两个整数，表示该田地的奶牛数量和避难所的容量。

接下来的P行：每行三个整数，表示连接两个田地的路径及其通过所需的时间。

输出格式

一个整数，表示所有奶牛都能到达避难所的最短时间。如果不可能，输出-1。

输入数据 1

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

输出数据 1

110

提示

输出详细信息：

在 110 个时间单位中，田地 1 的两头奶牛可以进入该田地的庇护所，田地 1 的四头奶牛可以进入田地 2 的庇护所，一头奶牛可以进入田地 3 并与田地 3 的庇护所下的奶牛汇合。尽管还有其他计划可以将所有奶牛都放在庇护所下，但没有一个计划会在少于 110 个时间单位内完成。

来源

USACO 2005 年 3 月金奖