背景

小明正在进行一场“环形冒险之旅”。地图上有 n (1≤n≤1,000,000) 座山，每座山上有一间房子，山编号为 1 到 n，这些山围成一个圆圈。

如果某座山上的房子内金币值为正数，表示小明进入该房子可以获得这些金币。

如果某座山上的房子内金币值为负数，表示小明进入该房子会失去这些金币。

金币值范围：-100000到100000。

游戏规则

小明会收到m次冒险任务 (1≤m≤100,000)。每个任务小明将会被直升机投放到第x座山上，同时会收到一个秘密数字y(1≤x, y≤ n)，y 表示路线要经过的房子总数（包括起点）。地图是环形的，当走到编号 n 之后，下一座山是编号 1。

在任务路线经过的房子（包括x），小明可以选择进或不进。

请你计算在所有 m 次冒险任务中，找出小明单次任务能获得的最高的金币数。

输入/输出例子2

输入：

5 2

3 -15 4 6 9

2 4

4 2

输出：

19数据范围：

30%数据：1≤n≤1000，1≤m≤1000，1≤x,y≤n，金币值范围：-100000到100000

50%数据：1≤n≤1000，1≤m≤1000，1≤x,y≤n，金币值范围：-100000到100000

100%数据：1≤n≤1,000,000，1≤m≤100,000，1≤x,y≤n，金币值范围：-100000到100000