You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

说明

有n（2<=n<=100000）个排成一个圆圈的整数，从位置1到位置n，每个都在-100到100之间，有m(m<=100000)个计算，每次两个整数x,y (0 < x， y <= n)，问从位置x到位置y数之和（如果是x<=y表示从x到y，如果是x>y，则表示从x到n再从1到y）。请问这m个计算结果中最大值是多少？

输入格式

第一行两个整数：n m 第二行n个整数 ，下面有m行，每行两个整数。

输出格式 一个整数。

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

23

提示

【数据范围】

20%，2 ≤ n,m ≤ 10000；

100%，2 ≤ n,m ≤ 100000；

另外，20%，x<=y。

来源 前缀和