题目描述

有 $N$ 个方格排成一行，从左到右编号为 $1, 2, \ldots, N$。

当你位于方格 $i$ 时，可以进行以下移动之一。

• 选择一个满足 $1 \leq j < i$ 的整数 $j$，移动到方格 $j$。该移动的代价为 $L_i$。
• 选择一个满足 $i < j \leq N$ 的整数 $j$，移动到方格 $j$。该移动的代价为 $R_i$。

给定 $Q$ 个查询，请逐一回答。每个查询的格式如下。

• 给定整数 $s$ 和 $t$。求从方格 $s$ 出发，通过反复移动到达方格 $t$ 所需的最小总代价。

输入格式

输入按以下格式从标准输入读入：

• $N$ $Q$
• $L_2$ $L_3$ $\ldots$ $L_N$
• $R_1$ $R_2$ $\ldots$ $R_{N - 1}$
• $\text{query}_1$
• $\text{query}_2$
• $\vdots$
• $\text{query}_Q$

其中，$\text{query}_i$ 是第 $i$ 个查询，格式如下：

• $s$ $t$

输出格式

输出 $Q$ 行。

第 $i$ 行应包含第 $i$ 个查询的答案。

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

3
3
1
5
3
2
9

下面解释第 1 个和第 2 个查询。

对于第 1 个查询，如果从方格 $1$ 直接移动到方格 $2$，总代价为 $R_1 = 3$，这是可能的最小总代价。

对于第 2 个查询，如果从方格 $2$ 移动到方格 $4$，再从方格 $4$ 移动到方格 $1$，总代价为 $R_2 + L_4 = 3$，这是可能的最小总代价。

数据范围

• $2 \leq N \leq 3 \times 10^5$

• $1 \leq Q \leq 3 \times 10^5$

• $1 \leq L_i \leq 10^9$ $(2 \leq i \leq N)$

• $1 \leq R_i \leq 10^9$ $(1 \leq i \leq N - 1)$

• 每个查询中 $1 \leq s, t \leq N$。

• 每个查询中 $s \neq t$。

• 所有输入值均为整数。

• 来源：AtCoder ABC 479 D

子任务设置

• 子任务 1（30 分）：$N, Q \le 2000$。
• 子任务 2（70 分）：无特殊限制。