人们居住在一个由山脉组成的村庄里。 山村由坐标平面上的 $N$ 个点组成。将这些点按 $x$ 坐标递增的顺序连接起来，就构成了山村的形状。 对于所有 $i$，第 $i$ 个点的位置为 $(i, H_i)$（保证 $\left\vert H_i - H_{i+1} \right\vert = 1$）。

山村的入口是山村的最左端点 $(1, H_1)$。同样，山村的出口是山村的最右端点 $(N, H_N)$。

山村中的重力作用方式比较特殊，有两种作用方式，由变量 $T$ 表示，其值为 1 或 2。

宇贤打算从山村入口出发，到达山村出口离开。

宇贤的状态始终处于“行走状态”和“飞行状态”之一。起初在入口处，宇贤处于“行走状态”。

在未到达出口时，宇贤可以进行以下操作：

1. 若处于“行走状态”（宇贤位于 $(i, H_i)$）：

   • 可以步行移动到 $(i+1, H_{i+1})$。此时消耗 $A_i$ 的体力。
   • 可以原地切换为“飞行状态”。

2. 若处于“飞行状态”（宇贤位于 $(i, j)$）：

   • 若 $i \le N-1$ 且 $H_{i+1} \le j$，可以飞行移动到 $(i+1, j)$。此时消耗 $F_i$ 的体力。
   • 可以通过自由落体移动到 $(i, H_i)$ 并切换为“行走状态”。此时，若 $T = 1$，消耗 $\left\lfloor \sqrt {j - H_i} \right\rfloor \times C_i$ 的体力；若 $T = 2$，消耗 $(j - H_i) \times C_i$ 的体力。

请编写一个程序，计算宇贤从山村入口出发到达出口所需的最少体力。

输入格式

第一行给出 $N$ 和 $T$。

第二行给出 $H_1, H_2, \ldots, H_N$，以空格分隔。

第三行给出 $A_1, A_2, \ldots, A_{N-1}$，以空格分隔。

第四行给出 $C_1, C_2, \ldots, C_N$，以空格分隔。

第五行给出 $F_1, F_2, \ldots, F_{N-1}$，以空格分隔。

（$2 \le N \le 10^5, 1 \le T \le 2$，对于所有 $i$，$1 \le H_i \le N$，$1 \le A_i, F_i \le 10^9, 1 \le C_i \le 10^6$，且满足对于所有 $i$，$\left\vert H_i - H_{i+1} \right\vert = 1$。）

输出格式

第一行输出问题的答案。

子任务

1. (2分) 满足对于所有 $i$，$H_i = i$。
2. (10分) $T = 1, N \le 3000$
3. (10分) $T = 2, N \le 3000$
4. (30分) $T = 1, N \le 5 \times 10^4$
5. (18分) $T = 2$，满足对于所有 $i$，$H_i = N - i + 1$。
6. (30分) $T = 2$

样例

样例输入 1

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

样例输出 1

56

样例输入 2

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

样例输出 2

33