时间限制： 1.0 秒

空间限制： 256 MB

问题描述

某公司要处理一个周期性的物流问题。

有 $n$ 个城市，第 $i$ 个城市在每周的第 $j(1≤j≤7)$ 天会生产 $a_{ij}$ 吨某种货物，同时需要消耗 $b_{ij}$ 吨该种货物。已知每周的产量等于消耗量（即 $a_{ij}$ 之和等于 $b_{ij}$ 之和）。

城市之间有 $m$ 条道路，第 $k$ 条道路连接了城市 $s_k$ 和 $t_k$。一条道路上运输 $1$ 吨货物有一个固定的成本 $c_k$。道路都可以双向使用。每天运输的货物量没有限制。城市之间的距离并不远，货物可以从任意一个城市运输到任意另一个城市并且在当天到达。

货物如果在当天没有被消耗掉，就需要存放在仓库里过夜。第 $i$ 个城市的仓库容量为 $v_i$，存放 $1$ 吨货物过一夜所需的成本是 $w_i$。

请你计算该公司如果每周循环性地按照一个固定的流程调度货物的话，该公司在最优方案下每周需要为货物的运输和存储消耗多少成本。

输入格式

从标准输入读入数据。

输入的第一行有两个正整数 $n$ 和 $m$，即城市的个数和道路的条数。

接下来有 $n$ 行，每行包含 $16$ 个整数，用以描述第 $i$ 个城市的相关数据。其中第 $i$ 行包含的数为 $a_{i1}, a_{i2}, a_{i3}, a_{i4}, a_{i5}, a_{i6}, a_{i7}, b_{i1}, b_{i2}, b_{i3}, b_{i4}, b_{i5}, b_{i6}, b_{i7}, v_i, w_i$。

接下来有 $m$ 行，每行包含 $3$ 个整数，用以描述一条道路的相关数据。其中第 $k$ 行包含的数为 $s_k,t_k,c_k$。

输入数据中城市的编号均为 $1$ 到 $n$ 之间。输入数据的每行的行首行尾均保证没有空格，两个数之间恰好被一个空格隔开。

输出格式

输出到标准输出。

输出一行一个整数，即最优方案下每周的支出。

3 3
0 0 0 0 5 0 0 0 0 0 0 0 0 0 2 4
0 0 0 0 0 0 0 2 0 0 0 0 0 0 2 1
0 0 0 0 0 0 0 0 0 3 0 0 0 0 2 5
1 2 1
1 3 5
2 3 1

67

样例 1 解释

城市 1 每周五生产 5 吨货物，把其中 2 吨运到存储费用低廉的城市 2 存储，把 1 吨运到城市 3 存储，剩下的 2 吨留在城市 1。

在次周一的时候城市 2 会消耗掉存放在那里的 2 吨货物。为了节约存储成本，将囤放在城市 1 的货物运到城市 2 存放。周三再将所有货物运到城市 3 以满足该城市的需求。

在此方案下，每周的运输成本为 8，每周的存储成本为 59，因此每周的总支出为 67。

子任务

对于 $100\%$ 的数据，保证：

• $1≤n≤100,1≤m≤500,0≤a_{ij},b_{ij},v_i≤100,1≤w_i,c_k≤100$；
• 道路不存在重边和自环；
• 不会出现未消耗完货物且无法全部存入仓库的情况；
• 不会出现当天生产货物量加仓库库存量小于当天消耗货物量的情况。