土地划分
题目描述
Y 国有 n 座城市和 m 条双向公路,任意两座城市都能经由公路到达。王位继承人 A 和 B 决定将领土一分为二。城市 1 归 A 国,城市 n 归 B 国。其余城市各划给其中一个国家,划分后每个国家内的城市可以不连通。
总评分按以下规则计算。
- 对于城市 i(2≤i≤n−1),划给 A 国获得 VAi 分,划给 B 国获得 VBi 分。城市 1 和 n 没有单独的评分。
- 对于第 i 条公路,两端都在 A 国时获得 EAi 分,两端都在 B 国时获得 EBi 分,分属两国时扣除 ECi 分。
求最高总评分。
输入格式
第一行有两个整数 n,m。
第二行有 n−2 个非负整数 VA2,…,VAn−1。第三行有 n−2 个非负整数 VB2,…,VBn−1。
接下来 m 行,第 i 行有五个整数 xi,yi,EAi,EBi,ECi,表示一条连接城市 xi,yi 的公路及其三种评分参数。公路两端的编号在 1 到 n 之间,三个评分参数均为非负整数。
输出格式
输出一行一个整数,表示最高总评分。
样例 #1
3 3
8
9
1 2 2 6 2
2 3 8 5 7
1 3 9 4 1
11
城市 2 划给 B 国时,总评分为 VB2+EB2−EC1−EC3=9+5−2−1=11。
数据范围
| 测试点 |
n 的上限 |
m 的上限 |
附加条件 |
| 1–2 |
20 |
200 |
无 |
| 3–4 |
5000 |
10000 |
所有 VAi,VBi,EAi,EBi 均为 0 |
| 5–6 |
所有 ECi 均为 0 |
| 7–10 |
10000 |
40000 |
无 |
题目保证评分的运算过程和最终结果均在 32 位有符号整数范围内。