Kuangyeye is a dalao of the ACM school team of Hunan University. His favorite food are hamburgers. One day, Kuangyeye came to the KFC(or maybe McDonald) and saw $n$ hamburgers on the counter. The weight of the $i$-th hamburger was $w_i$. Since he likes hamburgers very much, he would like to buy some hamburgers. Considering his weight or other factors, Kuangyeye only wanted to eat all the hamburgers from the $a$-th heaviest to the $b$-th. Since Kuangyeye is fickle, he had $k$ plans before buying hamburgers. The $i$-th plan gives $a_i$ and $b_i$. Please help Kuangyeye calculate the maximum weight of hamburgers he can eat among the $k$ plans.

The first line of input contains two integer $n$ and $k$ --the number of hamburgers on the counter
and the number of plans Kuangyeye had;
the next line contains $n$ integer--the $i$-th integer represents the weight of $i$-th hamburger, namely
$w_i$;
Each the following $k$ line contains two integer $a_i$ and $b_i$ ,represents Kuangyeye's strategy in his $i$-th plan.

Output contain a single integer, represents maximum weight of hamburgers Kuangyeye can eat.

Kuangyeye's first plan was to eat the hamburger weighing $6$;
and his second plan was to eat the hamburger weighing $3$ and $4$;
So the maximum weight of hamburgers he can eat was $7$.
$1≤n,k≤100000,1≤a_i≤b_i≤n,1≤w_i≤10000$.