241976 - 小 C 的账本

题目描述

小 C 开了一家小店,每天把当天的收支记在账本上。账本按照时间顺序记下了 n 天的收支情况:正数表示当天赚到的钱数,负数表示当天亏掉的钱数。

小 D 是小 C 的朋友,他从账本中圈出了 m 段时间,每段时间用两个整数 x 和 y 表示,即从第 x 天到第 y 天。

小 D 想知道:这 m 段时间里,总收支最大的那一段,它的总收支是多少?

请你编程帮助小 C 算出这个最大值。

输入

第一行包含两个整数 m 和 n。

第二行包含 n 个整数,表示账本上每天的收支。

接下来 m 行,每行包含两个整数 x 和 y,表示一段时间。

输出

共一行,输出一个整数,表示这 m 段时间总收支中的最大值。

样例

输入

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

输出

13

输入

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

输出

3
说明

数据范围

1 ≤ x ≤ y ≤ n。

1 ≤ n, m ≤ 100000。

每天的收支在 [−1000, 1000] 的范围内。

题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 19
通过人数 8
金币数量 4 枚
难度 入门


上一题 下一题