跳跳来到了第二个游戏，游戏规则为，跳跳有一个含有n个非负整数的数列与m个区间，每个区间可以表示为li,ri。
他要选择其中k个区间， 并使得这些区间的交的那些位置所对应的数的和最大。（是指k个区间共同的交，即每个区间都包含这一段，具体可以参照样例）

在样例中，5个位置对应的值分别为1,2,3,4,6，那么选择2,5与4,5两个区间的区间交为4,5，它的值的和为10。

第一行输入三个整数n,k,m(1<=n<=100000,1<=k<=m<=100000)。 
接下来一行n个整数ai，表示小A的数列(0<=ai<=10^9)。 
接下来m行，每行两个整数li,ri，表示每个区间(1<=li<=ri<=n)。

一行表示答案