时空限制

1S/512M

题目描述

数轴上有 $n$ 个站点，编号为 $1, 2, \dots, n$。对于 $1 \le i < n$，从站点 $i$ 到 $i+1$ 的通道长度为 $w_i$。

现有 $q$ 次移动任务，第 $j$ 次任务需要从站点 $l_j$ 移动到 $r_j$（$l_j < r_j$）。单次任务的总路程等于该区间内所有通道长度之和。

在执行所有任务之前，你可以选择一个位置 $i$（$1 \le i < n$），在站点 $i$ 和 $i+1$ 之间建造一个传送门。一旦建成，所有经过这条通道的任务都可以瞬间通过，即该通道的长度视为 $0$。

求最优地选择一个 $i$，使得所有任务的总路程之和最小。

格式

输入格式

第一行包含两个整数 $n$ 和 $q$。表示站点数量和移动任务个数。

第二行包含 $n-1$ 个整数 $w_1, w_2, \dots, w_{n-1}$，表示通道长度。

接下来 $q$ 行，每行输入两个整数 $l_j$ 和 $r_j$，表示移动任务的起点和终点。

输出格式

输出一个整数，表示所有任务的最小总路程。

样例

样例输入 #1

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

样例输出 #1

10

数据规模

注意：你只有通过了子任务的所有测试点，才能获得对应子任务的分数。

对于 $100\%$ 的数据，$2 \le n \le 2 \times 10^5$，$1 \le q \le 2 \times 10^5$，$1 \le w_i \le 10^6$，$1 \le l_j < r_j \le n$。