Background

有一天：

linka：muyang，IMO2019D1T1怎么做啊

muyang：我不会诶qaq，~~我去找找题解吧。~~

A few minutes later...

muyang：题解我看不懂诶，去问问dmy吧

linka：好吧

muyang & linka：dmy，这题怎么做啊qaq

dmy：这不是一道大水题嘛，就这么做balabala...

十分钟之后：

dmy：听懂了吗

muyang & linka：没有

为了膜拜dmy，muyang特此出了这道题，来表示自己“wzbl”的心理。

Description

dmy面前有\(n\)道题目，每道题目有一个难度\(a_i\)。

因为dmy要去\(AK IOI & IMO\)，所以他只有\(t\)的时间，在每个时间里，他可以在给定的\(m\)个区间，选择一个区间\(i\)，虐掉该区间里最难的一道题，他将得到与最难题的难度相同的分数。

dmy想要在\(t\)内得到最大的分数，但是如上面所说，他要\(AK IOI & IMO\)，所以这个任务就交给你了。

Format

Input

第一行，三个数，\(n\)，\(t\)，\(m\)，意思如题。

第二行，\(n\)个数，第\(i\)个数为\(a_i\)。

其后\(m\)行，每行两个数，代表一个区间。

Output

一行一个数，代表dmy能得到的最大分数。

Sample 1

Input

3 3 3  
1 2 3  
1 3  
1 3  
1 3  

Output

9

Limitation

1s, 125MiB每个点.

Hint

数据范围

对于\(40%\)的数据，\(n,t,m,r_i-l_i \le 100\)。

对于\(100%\)的数据，\(n \le 100000\)，\(a_i \le 10000\)，\(t \le m \le 100000\)，\(1 \le l_i \le r_i \le n\)，答案在\(int\)范围内。

特别的，有\(10%\)的数据，\(t = m\)。

特别提示：

任意两次dmy选择的区间编号\(i\)肯定是不同的，但任意两次选定的区间可能相同，具体见样例。

Source

By muyang_233
转载请经过原作者同意