3396. 度度熊的交易计划

单点时限: 1.0 sec

内存限制: 256 MB

度度熊参与了喵哈哈村的商业大会,但是这次商业大会遇到了一个难题:

喵哈哈村以及周围的村庄可以看做是一共由 个片区, 条公路组成的地区。由于生产能力的区别,第 个片区能够花费 元生产 1 个商品,但是最多生产 个。同样的,由于每个片区的购买能力的区别,第 个片区也能够以 的价格出售最多 个物品。

由于这些因素,度度熊觉得只有合理的调动物品,才能获得最大的利益。据测算,每一个商品运输 1 公里,将会花费 1 元。那么喵哈哈村最多能够实现多少盈利呢?

输入格式

第一行两个整数

接下来 行,每行四个整数 表示的第 个地区。

接下来 行,每行三个整数 ,表示该条公路连接 两个片区,距离为

可能存在重边,也可能存在自环。

输出格式

输出最多能赚多少钱。

样例

Input
2 1
5 5 6 1
3 5 7 7
1 2 1
Output
23

6 人解决,6 人已尝试。

6 份提交通过,共有 12 份提交。

5.9 EMB 奖励。

创建: 2 年,3 月前.

修改: 2 年,3 月前.

最后提交: 1 年,9 月前.

来源: 2017 百度之星程序设计大赛

题目标签