You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小龙最近研究出了一个非常快的芯片, 他正在计算制作此芯片的花费.

制作芯片的花费可以抽象为一张 $2 \times n$ 的网格图，你要从左上角 $(1,1)$ 走到右下角 $(2, n)$ .

在格子中, 只能向右, 或者向上, 或者向下移动, 每次移动一格, 会有一个对应的花费. 相当于格子之间有一条带权边.

小龙很聪明, 他很快找出了一种行走方案, 并且计算出了最小花费$cost_1$

突然, 小龙接到了电话, 电话告诉他需要额外支付一些专利费.

专利费可以抽象为额外的 $m$ 条限制.

每条限制形如：给定 $i, j, x$，如果你同时走了格子 $(1, i)$ 到 格子$(1, i+1)$ 和 格子$(2, j)$ 到格子 $(2, j+1)$ 这两条边，那么你就需要额外 $x$ 的花费。

制作芯片的花费加上专利费等于最终花费.

现在小龙需要重新制作一种行走方案, 使得从左上角 $(1,1)$ 走到右下角 $(2, n)$所花的最终花费最小, 最小值记为$cost_2$

小龙现在想请教你, 因为专利费的缘故, 芯片多花了多少钱, 即$cost_2 - cost_1$等于多少?

• 注意$1$：$cost_2$的计算并不需要单独考虑最小的制作芯片的花费, 而是找到一种行走方案, 使得芯片的花费加上专利费的和最小即可.

• 注意$2$：给的$m$条限制中，可能有重复的$(i, j)$, 但保证在二元组内部, $i!=j$.

输入格式

第一行两个正整数 $n, m$ 。

接下来三行，依次描述第一行格子向右行走的费用, 上下行走的费用, 第二行格子向右行走的费用。

其中第一行有 $n-1$ 个正整数，第 $i$ 个数表示 $(1, i)$ 到 $(1, i+1)$ 的边权$a_i$。

第二行有 $n$ 个正整数，第 $i$ 个数表示 $(1, i)$ 和 $(2, i)$ 间的边权$b_i$。上下行走的费用是相同的。

第三行有 $n-1$ 个正整数，第 $i$ 个数表示 $(2, i)$ 到 $(2, i+1)$ 的边权$c_i$。

接下来 $m$ 行，每行三个正整数 $i, j, x(1 \leq i, j<n)$ ，表示一个专利费用的限制。

输出格式

一行一个整数，表示答案。

样例 #1

样例输入 #1

5 2
2 3 5 2
6 1 2 1 1
1 2 4 2
1 4 4
2 3 1

样例输出 #1

2

样例 #2

样例输入 #2

4 2
1 1 1
1000 1 10 1000
1 1 1
1 2 1000
2 3 1

样例输出 #2

10

样例 #3/#4/#5

见下发文件中ex_cost3/4/5.in/out

样例解释

对于样例$1$:

如果考虑专利限制, 可以$(1, 1)\rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (1, 4) \rightarrow (1, 5) \rightarrow (2, 5)$, 最小总花费是13. 如果不考虑专利限制, 可以$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow (2, 4) \rightarrow (2, 5)$, 最小花费是11, 因此差2.

对于样例$2$:

如果考虑专利限制, 可以$(1, 1) \rightarrow (1, 2) \rightarrow (1, 3) \rightarrow (2, 3) \rightarrow (2, 4)$, 最小总花费是14. 如果不考虑专利限制, 可以$(1, 1) \rightarrow (1, 2) \rightarrow (2, 2) \rightarrow (2, 3) \rightarrow ( 2, 4)$, 最小花费是4, 因此差10.

数据范围

保证 $1 \leq n \leq 500$, $1 \leq m \leq 1000$，$1 ≤ a_i, b_i, c_i, x ≤ 10^9$

对于$20\%$的数据：保证 $n≤6$

对于$40 \%$的数据：保证 $n≤18$

对于另外$30\%$的数据：保证专利限制中的 $|i−j|≤12$

对于$100\%$的数据：无特殊限制

其他要求

每个测试点时限：$2$s 内存上限：$512$M