土地划分
时间限制：10s 空间限制：256MB
题目描述
Y国有N座城市，并且有M条双向公路将这些城市连接起来，并且任意两个城市至少有一条路径可以互达。
Y国的国王去世之后，他的两个儿子A和B都想成为新的国王，但他们都想让这个国家更加安定，不会用武力解决问题。
于是他们想将这个国家分成两个小国家A国和B国。现在，A拥有1号城市，B拥有N号城市，其他的城市还尚未确定归属哪边（划分之后的国家内部城市可以不连通）。
由于大家都想让国家变得更好，而某些城市的人民愿意国王的A儿子作为他们的领袖，而某些城市更看好B，而为了交通的便捷，如果划分后的公路连接两个同一个国家的城市，那么更利于城市之间的交流。于是大臣们设计了一种对土地划分的评分机制，具体如下：
1. 对于城市i，如果它划分给A国，将得到VA[i]的得分；划分给B国，将得到VB[i]的得分。
2. 对于一条公路i，如果它连接两个A国的城市，将得到EA[i]的得分；连接两个B国的城市，将得到EB[i]的得分；否则，这条公路将失去意义，将扣除EC[i]的得分。
现请你找到最优的土地划分，使得这种它的评分最高。
输入格式
第一行包含两个整数N，M，含义如问题描述所示。
接下来一行N-2个非负整数，表示VA[2..N-1]。
接下来一行N-2个非负整数，表示VB[2..N-1]。
接下来M行，每行五个非负整数描述一条公路：X Y EA[i] EB[i] EC[i]，含义如问题描述所示。
输出格式
输出有且仅有一个整数，表示最高评分。
样例输入
3 3 8 9 1 2 2 6 2 2 3 8 5 7 1 3 9 4 1
样例输出
11 【样例说明】 A国仅有1号点，B国有2号和3号点。 评分=VB[2]+EB[2]-EC[1]-EC[3]=9+5-2-1=11。
提示
【数据说明】
数据点 N M 备注
1-2 <=20 <=200 无
3-4 <=5000 <=10000 VA、VB、EA、EB均为0
5-6 <=5000 <=10000 EC均为0
7-10 <=10000 <=40000 无
保证运算过程中及最终结果不超过32位带符号整数类型的表示范围
题目来源
没有写明来源