D - Choosing Flowers for the Flower Bed Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MiB

配点 : 400 点

問題文

高橋君は庭に花壇を作ろうとしています。

園芸店には N 種類の花の苗が売られており、それぞれの花には 1 から N までの番号が付けられています。高橋君は各花の見た目を確認し、花 i に対して美しさ S_i を評価しました（美しさは負の値になることもあります）。

高橋君はこの N 種類の花の中からいくつかを選んで花壇に植えます。ただし、選べる花の種類数は 0 以上 K 以下です。各花について「選んで 1 つ植える」か「選ばない」かのいずれかを決めます。

また、高橋君の住む街では M 個のガーデニングコンテストが開催されます。コンテスト j の参加条件は、番号が L_j 以上 R_j 以下の花のうち少なくとも 1 種類が花壇に植えられていることです。参加条件を満たしたコンテストには必ずすべて参加しなければならず（参加を辞退することはできません）、コンテスト j に参加すると賞金 P_j を得られます。

高橋君は植える花の集合をうまく選ぶことで、（選んだ花の美しさの合計）+（参加するすべてのコンテストの賞金の合計）を最大化したいと考えています。

この値の最大値を求めてください。なお、1 種類も花を選ばないことも許され、その場合は美しさの合計および賞金の合計はいずれも 0 となります。

制約

  • 1 \leq N \leq 15
  • 1 \leq K \leq N
  • 1 \leq M \leq 15
  • -1000 \leq S_i \leq 1000 （1 \leq i \leq N）
  • 1 \leq L_j \leq R_j \leq N （1 \leq j \leq M）
  • 1 \leq P_j \leq 1000 （1 \leq j \leq M）
  • 入力はすべて整数である

入力

N K M
S_1 S_2 \ldots S_N
L_1 R_1 P_1
L_2 R_2 P_2
\vdots
L_M R_M P_M
  • 1 行目には、花の種類数を表す N 、花壇に植える花の最大種類数を表す K 、コンテストの個数を表す M が、スペース区切りで与えられる。
  • 2 行目には、各花の美しさを表す S_1, S_2, \ldots, S_N が、スペース区切りで与えられる。
  • 3 行目から M 行にわたり、各コンテストの情報が与えられる。
  • 2 + j 行目では、コンテスト j の参加条件となる花の番号の範囲の左端 L_j 、右端 R_j 、および参加時に得られる賞金 P_j が、スペース区切りで与えられる。

出力

（選んだ花の美しさの合計）+（参加するすべてのコンテストの賞金の合計）の最大値を 1 行で出力せよ。

入力例 1

3 2 1
5 3 -2
1 2 10

出力例 1

18

入力例 2

3 1 2
-10 -10 -10
1 1 3
2 3 2

出力例 2

0

入力例 3

6 3 4
10 -5 8 -3 7 -1
1 3 15
2 5 20
4 6 10
1 6 5

出力例 3

75

入力例 4

10 5 8
100 -50 80 -30 70 -10 60 -40 90 -20
1 3 200
2 5 150
4 7 180
6 10 120
1 5 100
3 8 90
5 10 110
1 10 50

出力例 4

1400

入力例 5

1 1 1
-1000
1 1 1

出力例 5

0

Score : 400 pts

Problem Statement

Takahashi is trying to create a flower bed in his garden.

A gardening shop sells seedlings of N types of flowers, each numbered from 1 to N. Takahashi examined the appearance of each flower and assigned a beauty value S_i to flower i (beauty values can be negative).

Takahashi will select some of these N types of flowers to plant in the flower bed. However, the number of types of flowers he can select is between 0 and K, inclusive. For each flower, he decides either to "select it and plant one" or "not select it."

Additionally, M gardening contests are held in the town where Takahashi lives. The participation condition for contest j is that at least one type of flower with a number between L_j and R_j (inclusive) is planted in the flower bed. He must participate in all contests whose conditions are satisfied (he cannot decline participation), and by participating in contest j, he receives a prize of P_j.

Takahashi wants to choose the set of flowers to plant in order to maximize (the sum of beauty values of the selected flowers) + (the sum of prizes from all contests he participates in).

Find the maximum value of this quantity. Note that it is allowed to select no flowers at all, in which case both the sum of beauty values and the sum of prizes are 0.

Constraints

  • 1 \leq N \leq 15
  • 1 \leq K \leq N
  • 1 \leq M \leq 15
  • -1000 \leq S_i \leq 1000 (1 \leq i \leq N)
  • 1 \leq L_j \leq R_j \leq N (1 \leq j \leq M)
  • 1 \leq P_j \leq 1000 (1 \leq j \leq M)
  • All input values are integers

Input

N K M
S_1 S_2 \ldots S_N
L_1 R_1 P_1
L_2 R_2 P_2
\vdots
L_M R_M P_M
  • The first line contains N, the number of types of flowers, K, the maximum number of types of flowers that can be planted in the flower bed, and M, the number of contests, separated by spaces.
  • The second line contains the beauty values of each flower S_1, S_2, \ldots, S_N, separated by spaces.
  • The following M lines provide information about each contest.
  • The (2 + j)-th line contains the left endpoint L_j and right endpoint R_j of the range of flower numbers that form the participation condition for contest j, and the prize P_j received upon participation, separated by spaces.

Output

Output the maximum value of (the sum of beauty values of the selected flowers) + (the sum of prizes from all contests participated in) on a single line.

Sample Input 1

3 2 1
5 3 -2
1 2 10

Sample Output 1

18

Sample Input 2

3 1 2
-10 -10 -10
1 1 3
2 3 2

Sample Output 2

0

Sample Input 3

6 3 4
10 -5 8 -3 7 -1
1 3 15
2 5 20
4 6 10
1 6 5

Sample Output 3

75

Sample Input 4

10 5 8
100 -50 80 -30 70 -10 60 -40 90 -20
1 3 200
2 5 150
4 7 180
6 10 120
1 5 100
3 8 90
5 10 110
1 10 50

Sample Output 4

1400

Sample Input 5

1 1 1
-1000
1 1 1

Sample Output 5

0