土地划分

题目描述

$Y$ 国有 $N$ 座城市,并且有 $M$ 条双向公路将这些城市连接起来,并且任意两个城市至少有一条路径可以互达。$Y$ 国的国王去世之后,他的两个儿子 A 和 B 都想成为新的国王,但他们都想让这个国家更加安定,不会用武力解决问题。于是他们想将这个国家分成两个小国家 A 国和 B 国。现在,A 拥有 $1$ 号城市,B 拥有 $N$ 号城市,其他的城市还尚未确定归属哪边(划分之后的国家内部城市可以不连通)。由于大家都想让国家变得更好,而某些城市的人民愿意国王的 A 儿子作为他们的领袖,而某些城市更看好 B,而为了交通的便捷,如果划分后的公路连接两个同一个国家的城市,那么更利于城市之间的交流。于是大臣们设计了一种对土地划分的评分机制,具体如下:对于城市 $i$,如果它划分给 A 国,将得到 $\mathit{VA}_i$ 的得分;划分给 B 国,将得到 $\mathit{VB}_i$ 的得分。对于一条公路 $i$,如果它连接两个 A 国的城市,将得到 $\mathit{EA}_i$ 的得分;连接两个 B 国的城市,将得到 $\mathit{EB}_i$ 的得分;否则,这条公路将失去意义,将扣除 $\mathit{EC}_i$ 的得分。现请你找到最优的土地划分,使得这种它的评分最高。

输入输出格式

输入格式


第一行包含两个整数 $N$,$M$,含义如问题描述所示。接下来一行 $N-2$ 个非负整数,表示 $\mathit{VA}_2,\mathit{VA}_3,\cdots,\mathit{VA}_{N-1}$。接下来一行 $N-2$ 个非负整数,表示 $\mathit{VB}_2,\mathit{VB}_3,\cdots,\mathit{VB}_{N-1}$。接下来 $M$ 行,每行五个非负整数描述一条公路:$X,Y,\mathit{EA}_i,\mathit{EB}_i,\mathit{EC}_i$,含义如问题描述所示。

输出格式


输出有且仅有一个整数,表示最高评分。

输入输出样例

输入样例 #1

3 3 
8 
9 
1 2 2 6 2 
2 3 8 5 7 
1 3 9 4 1

输出样例 #1

11

说明

对于全部数据,$n \le 10^4$,$m \le 4\times 10^4$。 保证运算过程中及最终结果不超过 $32$ 位带符号整数类型的表示范围。