4275 - 구간의 합

Time Limit: 1s Memory Limit: 128MB

Submissions: 326 Solved: 88
Description

N개의 숫자와 M개의 구간이 주어졌을 때, 구간에 해당하는 모든 숫자를 합하여 구할 수 있는 합 중 가장 큰 합을 구하고자 한다. 하나의 구간은 숫자의 시작 위치 a와 마지막 위치 b로 정의되어 있다. (각 위치는 0부터 시작)

Input

* Line 1 : 2개의 정수, N M (1≤N, M≤100,000)

* Line 2 : 공백으로 구분된 N개의 정수 

* Line 3~M+2 : 2개의 정수, a b

    - a : 숫자의 시작위치

    - b : 숫자의 마지막 위치 

Output

구간의 합 중 가장 큰 합을 정수로 출력. (합은 INT의 범위를 넘지 않음)

Sample Input
10 3
-3 1 8 7 2 -20 15 30 -60 40
0 2
5 7
9 9
Sample Output
40