Problem Description

AtCoder Cafe has $ N $ meals, numbered from $ 1 $ to $ N $. The deliciousness of meal $i\ (1\ \leq\ i\ \leq\ N)$ is $ a_i $.
Square1001 will eat at AtCoder Cafe for $ Q $ days. On day $i\ (1\ \leq\ i\ \leq\ Q)$, he will choose the meal with the highest deliciousness value among those numbered from $ l_i $ to $ r_i $. If there are no such meals, he will leave without eating.

You are a demon and can use your magic to erase $ M $ out of $ N $ meals from the menu, making them unselectable. Your goal is to minimize the total deliciousness of the meals Square1001 chooses.
Find the minimum total deliciousness of the meals Square1001 chooses.

Input Format

The input is given from the standard input in the following format:

$ N $ $ M $ $ Q $ $a_1\ a_2\ a_3\ \cdots\ a_N$ $l_1\ r_1$ $l_2\ r_2$ $l_3\ r_3$ : : $l_Q\ r_Q$

Output Format

Output the minimum total deliciousness of the meals Square1001 chooses in one line.

Sample Input and Output

Sample Input #1

5 2 5
4 9 6 3 8
1 3
2 4
3 5
1 4
2 5

Sample Output #1

27

Sample Input #2

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

Sample Output #2

21

Sample Input #3

8 5 3
1 1 1 1 1 1 1 1
2 5
1 3
6 8

Sample Output #3

1

Notes/Hints

Constraints

• $ N $ is an integer between $ 1 $ and $ 50 $ inclusive.
• $ M $ is an integer between $ 0 $ and $ N $ inclusive.
• $ Q $ is an integer between $ 1 $ and $ 50 $ inclusive.
• $a_i\ (1\ \leq\ i\ \leq\ N)$ is an integer between $ 1 $ and $1\ 000\ 000\ 000$ inclusive.
• $l_i,\ r_i$ are integers satisfying $1\ \leq\ l_i\ \leq\ r_i\ \leq\ N$.

Subtasks

Subtask $ 1 $ \[$ 60 $ points\]

• $N\ \leq\ 15$.
• $Q\ =\ 1$.

Subtask $ 2 $ \[$ 60 $ points\]

• $N\ \leq\ 15$.

Subtask $ 3 $ \[$ 250 $ points\]

• For all $i\ (1\ \leq\ i\ \leq\ N)$, $a_i\ =\ 1$.

Subtask $ 4 $ \[$ 630 $ points\]

• No additional constraints.

Sample Explanation 1

If you erase meals numbered $ 2 $ and $ 3 $, the maximum deliciousness values for each day will be $ 4 $, $ 3 $, $ 8 $, $ 4 $, and $ 8 $, summing up to $ 27 $.

见题面 Input 部分

见题面 Output 部分