Problem #3396 - ECNU Online Judge

单点时限: 1.0 sec

内存限制: 256 MB

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

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

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

输入格式

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

接下来 $n$ 行，每行四个整数 $a_{i}, b_{i}, c_{i}, d_{i}$ $(1 \leq a_{i}, b_{i}, c_{i}, d_{i} \leq 1000)$ 表示的第 $i$ 个地区。

接下来 $m$ 行，每行三个整数 $u_{i}, v_{i}, k_{i}$ ，表示该条公路连接 $u_{i}, v_{i}$ $(1 \leq u_{i}, v_{i} \leq n)$ 两个片区，距离为 $k_{i}$ $(1 \leq k_{i} \leq 1000)$ 。

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

输出格式

输出最多能赚多少钱。

样例

Input

Output

9 人解决，10 人已尝试。

13 份提交通过，共有 74 份提交。

5.9 EMB 奖励。

创建: 7 年，5 月前.

修改: 7 年，5 月前.

最后提交: 2 周，2 天前.

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

flows

3396. 度度熊的交易计划

输入格式

输出格式

样例

服务

开源

关于我们