题目描述

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 \dots N-1]$。

接下来一行 $n-2$ 个非负整数，表示 $VB[2 \dots 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$。

数据说明

保证运算过程中及最终结果不超过 32 位带符号整数类型的表示范围。