Circular Route Query Distance

distances[i] connects station i and station (i+1) modulo n. Each query is an independent start and end; take the shorter of the clockwise and counterclockwise distances, then sum over all queries.

输入格式

The first line contains n q, the second line contains n edge lengths, followed by q lines of 0-based start and end stations. The original gives no value ranges; this site sets 1≤n,q≤100000, 1≤(edge length)≤10⁹.

输出格式

Output a single integer answer.

样例 1

输入：

4 3
1 2 3 4
0 1
1 3
3 0

输出：

10

样例 2

输入：

4 2
7 10 1 12
0 2
2 1

输出：

23

样例 3

输入：

1 1
9
0 0

输出：

0

样例说明

Example 1: the shortest distances are 1, 5 and 4, for a total of 10. Example 2: 0 to 2 goes the other way for 13, and 2 to 1 is 10, for a total of 23. Example 3: the same station needs no movement, for a total of 0.