3396. 度度熊的交易计划

单点时限: 1.0 sec

内存限制: 256 MB

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

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

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

输入格式

第一行两个整数 $n,m$ $(1 \le n \le 500, 1 \le m \le 1000)$。

接下来 $n$ 行,每行四个整数 $a_i, b_i, c_i, d_i$ $(1 \le a_i, b_i, c_i, d_i \le 1000)$ 表示的第 $i$ 个地区。

接下来 $m$ 行,每行三个整数 $u_i, v_i, k_i$,表示该条公路连接 $u_i, v_i$ $(1 \le u_i, v_i \le n)$ 两个片区,距离为 $k_i$ $(1 \le k_i \le 1000)$。

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

输出格式

输出最多能赚多少钱。

样例

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

8 人解决,8 人已尝试。

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

5.3 EMB 奖励。

创建: 2 年,10 月前.

修改: 2 年,10 月前.

最后提交: 1 月,3 周前.

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

题目标签