F - Lunch Menu Editorial /

Time Limit: 2 sec / Memory Limit: 256 MB

配点：1000 点

問題文

AtCoder カフェでは N 個の食事があり, 番号が 1 から N までつけられている. 食事 i \ (1 \leq i \leq N) のおいしさは a_i である.
square1001 君は, Q 日間 AtCoder カフェで食事をする. i \ (1 \leq i \leq Q) 日目の食事では, 番号が l_i 以上 r_i 以下の食事の中から最もおいしさの値が大きいものを選ぶ. また, そのような食事がない場合は食事をせずに帰る.

あなたは悪魔であり, 魔力で N 個中 M 個の食事をメニューからかき消して選べないようにすることができる. あなたの目的は square1001 君の選ぶ食事のおいしさの合計を最小化することである.
square1001 君の選ぶ食事のおいしさの合計の最小値を求めなさい.

入力

入力は以下の形式で標準入力から与えられる. 

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

出力

square1001 の選ぶ食事のおいしさの合計の最小値を, 1 行で出力しなさい.

制約

  • N は 1 以上 50 以下の整数.
  • M は 0 以上 N 以下の整数.
  • Q は 1 以上 50 以下の整数.
  • a_i \ (1 \leq i \leq N) は 1 以上 1 \ 000 \ 000 \ 000 以下の整数.
  • l_i, r_i は 1 \leq l_i \leq r_i \leq N を満たす整数.

小課題

小課題 1 [60 点]

  • N \leq 15.
  • Q = 1.

小課題 2 [60 点]

  • N \leq 15.

小課題 3 [250 点]

  • すべての i \ (1 \leq i \leq N) に対して, a_i = 1.

小課題 4 [630 点]

  • 追加の制約はない.

入力例 1

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

出力例 1

27

もしあなたが番号 2, 3 の食事を消すと, それぞれの日の美味しさの最大値は 4, 3, 8, 4, 8 となり, 合計が 27 となる.

入力例 2

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

出力例 2

21

入力例 3

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

出力例 3

1

Max Score：1000 points

Problem Statement

There are N foods in AtCoder Café, which is conveniently numbered 1 through N. The deliciousness of food i is exactly a_i.
square1001 is going to have Q lunches. In i-th lunch, he will select the most delicious food (the food which has highest deliciousness) among the food which the number is between l_i and r_i (inclusive). If there are no such food, he won't eat lunch this time.

You are devil and you can erase M foods from the lunch menu and their menu will no longer able to select. Your objective is to minimize the total deliciousness of food square1001 selects.
Calculate the minimum value of total deliciousness of food square1001 selects.

Input

Input is given from 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

Print the minimum value of total deliciousness of food square1001 selects, in one line.

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 which holds 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]

  • a_i = 1 for all i \ (1 \leq i \leq N).

Subtask 4 [630 points]

  • There is no additional constraints.

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

If you delete food 2 and 3, the maximum deliciousness is 4, 3, 8, 4, 8 in order.
The total deliciousness is 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