E - 広告キャンペーンの選択 解説 /

実行時間制限: 2 sec / メモリ制限: 1024 MiB

配点 : 466 点

問題文

高橋君は、あるオンラインショップのマーケティング担当者です。このショップでは N 種類の商品を販売しており、商品 i の利益は V_i 円です。

高橋君は広告キャンペーンを実施する計画を立てています。利用可能な広告キャンペーンは M 種類あり、各キャンペーン j は商品 L_j から商品 R_j までの連続した商品（商品 L_j, L_j+1, \ldots, R_j）を宣伝対象としています。

キャンペーンを実施すると、その宣伝対象となっている商品がすべて売れます。同じ商品が複数のキャンペーンで宣伝されていても問題ありませんが、その商品の利益は 1 回だけ合計に加算されます。

高橋君は予算の都合上、ちょうど K 種類のキャンペーンを選んで実施することにしました。

K 種類のキャンペーンを選んで実施したとき、売れる商品から得られる利益の合計の最大値を求めてください。

制約

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq \min(M, 10)
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • 入力はすべて整数

入力

N M K
V_1 V_2 \ldots V_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • 1 行目には、商品の種類数 N 、キャンペーンの種類数 M 、実施するキャンペーンの数 K が、スペース区切りで与えられる。
  • 2 行目には、各商品の利益 V_1, V_2, \ldots, V_N が、スペース区切りで与えられる。
  • 3 行目から M 行では、各キャンペーンが宣伝対象とする商品の範囲が与えられる。
  • 2 + j 行目では、キャンペーン j が宣伝対象とする商品の範囲の左端 L_j と右端 R_j が、スペース区切りで与えられる。

出力

K 種類のキャンペーンを選んで実施したとき、売れる商品から得られる利益の合計の最大値を 1 行で出力せよ。

入力例 1

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

出力例 1

14

入力例 2

6 5 1
10 2 8 6 3 7
1 3
2 5
4 6
3 3
1 6

出力例 2

36

入力例 3

12 10 3
5 9 2 6 4 8 3 7 10 1 11 12
1 4
3 6
5 8
7 10
9 12
2 9
1 12
4 4
6 11
2 3

出力例 3

78

入力例 4

25 22 7
4 15 8 23 16 42 7 31 5 18 27 11 36 9 14 22 6 40 3 29 12 34 20 10 25
1 5
6 10
11 15
16 20
21 25
1 10
5 15
10 20
15 25
3 8
7 13
12 18
18 25
2 22
4 4
9 9
14 17
19 23
1 25
6 6
8 21
11 24

出力例 4

467

入力例 5

1 1 1
1000000000
1 1

出力例 5

1000000000

入力例 6

30 25 3
5 12 7 20 3 15 8 30 2 25 11 6 18 4 22 9 14 1 27 10 16 13 24 19 21 17 23 26 28 29
1 5
3 10
6 12
11 15
14 20
19 25
14 21
22 24
5 5
10 10
15 15
20 20
25 25
2 8
7 13
13 17
21 27
4 11
9 14
12 19
1 1
30 30
22 24
15 19
3 8

出力例 6

348

Score : 466 pts

Problem Statement

Takahashi is a marketing manager for an online shop. The shop sells N types of products, and the profit of product i is V_i yen.

Takahashi is planning to run advertising campaigns. There are M types of available advertising campaigns, and each campaign j targets a consecutive range of products from product L_j to product R_j (products L_j, L_j+1, \ldots, R_j).

When a campaign is run, all products targeted by that campaign are sold. It is fine for the same product to be targeted by multiple campaigns, but the profit from that product is added to the total only once.

Due to budget constraints, Takahashi has decided to select and run exactly K campaigns.

Find the maximum total profit obtainable from the products sold when exactly K campaigns are selected and run.

Constraints

  • 1 \leq N \leq 10^5
  • 1 \leq M \leq 10^5
  • 1 \leq K \leq \min(M, 10)
  • 1 \leq V_i \leq 10^9 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • All inputs are integers

Input

N M K
V_1 V_2 \ldots V_N
L_1 R_1
L_2 R_2
\vdots
L_M R_M
  • The first line contains the number of product types N, the number of campaign types M, and the number of campaigns to run K, separated by spaces.
  • The second line contains the profit of each product V_1, V_2, \ldots, V_N, separated by spaces.
  • From the 3rd line to the next M lines, the range of products targeted by each campaign is given.
  • The (2 + j)-th line contains the left endpoint L_j and right endpoint R_j of the range of products targeted by campaign j, separated by spaces.

Output

Print in one line the maximum total profit obtainable from the products sold when exactly K campaigns are selected and run.

Sample Input 1

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

Sample Output 1

14

Sample Input 2

6 5 1
10 2 8 6 3 7
1 3
2 5
4 6
3 3
1 6

Sample Output 2

36

Sample Input 3

12 10 3
5 9 2 6 4 8 3 7 10 1 11 12
1 4
3 6
5 8
7 10
9 12
2 9
1 12
4 4
6 11
2 3

Sample Output 3

78

Sample Input 4

25 22 7
4 15 8 23 16 42 7 31 5 18 27 11 36 9 14 22 6 40 3 29 12 34 20 10 25
1 5
6 10
11 15
16 20
21 25
1 10
5 15
10 20
15 25
3 8
7 13
12 18
18 25
2 22
4 4
9 9
14 17
19 23
1 25
6 6
8 21
11 24

Sample Output 4

467

Sample Input 5

1 1 1
1000000000
1 1

Sample Output 5

1000000000

Sample Input 6

30 25 3
5 12 7 20 3 15 8 30 2 25 11 6 18 4 22 9 14 1 27 10 16 13 24 19 21 17 23 26 28 29
1 5
3 10
6 12
11 15
14 20
19 25
14 21
22 24
5 5
10 10
15 15
20 20
25 25
2 8
7 13
13 17
21 27
4 11
9 14
12 19
1 1
30 30
22 24
15 19
3 8

Sample Output 6

348