小 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] 的范围内。