有一个 $2 \times n$ 的网格，你需要从左上角 $(1, 1)$ 走到右下角 $(2, n)$。每条边都有一个权值，此外还有 $m$ 个附加约束。每个约束由三个整数 $i, j$ 和 $c$ 描述。其含义是：如果你同时经过了边 $(1, i)$ 到 $(1, i + 1)$ 和边 $(2, j)$ 到 $(2, j + 1)$，你将额外产生 $c$ 的代价。

求路径上所有边的权值之和加上所产生的额外代价之和的最小值。

输入格式

第一行包含两个整数 $n$ 和 $m$ ($1 \le n \le 500; 1 \le m \le 1000$)。

接下来的三行描述每条边的权值： 第一行包含 $n - 1$ 个整数，其中第 $i$ 个整数表示从 $(1, i)$ 到 $(1, i + 1)$ 的边的权值。 第二行包含 $n$ 个整数，其中第 $i$ 个整数表示 $(1, i)$ 和 $(2, i)$ 之间的边的权值。 第三行包含 $n - 1$ 个整数，其中第 $i$ 个整数表示从 $(2, i)$ 到 $(2, i + 1)$ 的边的权值。

所有边权均为正整数且不超过 $10^9$。

接下来的 $m$ 行，每行包含三个整数 $i, j$ 和 $c$，表示一个约束 ($1 \le i, j < n; 1 \le c \le 10^9$)。

输出格式

输出一行，包含一个整数，即问题的答案。

样例

样例输入 1

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

样例输出 1

13