Problem B: Big Sum

Problem B: Big Sum

Time Limit: 1 Sec  Memory Limit: 128 MB
Submit: 24  Solved: 13
[Submit] [Status] [Web Board] [Creator:]

Description

Zser has recently become fascinated with data structures, and after a year of training, Zser feels that all interval problems are very simple. All you need to do is to build a data structure model and then set up a template. But Zser was stuck with a data structure problem when he played last night. Now Zser wants to ask you how to solve this problem. There is an array of length N, which contains N elements (element index starts from 1). For this array, there are Q queries, each query has two positive integers L, R, representing an interval in the array, and then sum. Now you need to sort the array so that after sorting, the sum of the Q queries is the largest.

Input

The first line input an integer N(1 <= N <= 200000) 
The second line input an integer Q(1 <= Q <= 200000) 
The Third line input N integers Ai(0 <= Ai <= 200000) 
The lines 4 - 4 + Q, each line with two positive integers l, R 

Output

Output the ans.

Sample Input Copy

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

Sample Output Copy

26