Problem Description

小A有一个含有$n$个非负整数的数列与$m$个区间。每个区间可以表示为$l_{i},r_{i}$。

它想选择其中$k$个区间， 使得这些区间的交的那些位置所对应的数的和最大。

例如样例中，选择$[2,5]$与$[4,5]$两个区间就可以啦。

Input

多组测试数据

第一行三个数$n,k,m(1\leq n\leq 100000,1\leq k\leq m\leq 100000)$。

接下来一行$n$个数$a_{i}$，表示lyk的数列$(0\leq a_{i}\leq 10^{9})$。

接下来$m$行，每行两个数$l_{i},r_{i}$，表示每个区间$(1\leq l_{i}\leq r_{i}\leq n)$。

Output

一行表示答案

5 2 3
1 2 3 4 6
4 5
2 5
1 4

10