← 返回题目列表

AtCoder · awc0057_d

D. 为花坛选择鲜花

中文机器翻译题面 查看原题

分数: 400 分

问题陈述

高桥正试图在他的花园里建造一个花坛。

一家园艺店出售幼苗 N 花的类型,每种编号从 1 to N。高桥检查了每朵花的外观并指定了美丽值 S_i 要花 i (美感值可以为负)。

高桥将选择其中一些 N 花坛中种植的花卉类型。然而,他可以选择的花朵种类数量介于 0 和 K,包括在内。对于每一朵花,他决定“选择它并种植一朵”或“不选择它”。

此外, M 高桥居住的小镇举行园艺比赛。竞赛参与条件 j 是至少一种类型的花,其数字介于 花坛内种植 L_j 和 R_j (含)。他必须参加所有满足条件的比赛(他不能拒绝参加),并且通过参加比赛 j,他获得的奖品为 P_j.

高桥想要选择要种植的花组,以便最大化(所选花的美丽值的总和) + (他参加的所有比赛的奖金总和)。

找到该数量的最大值。请注意,可以完全不选择花朵,在这种情况下,美丽值总和和奖品总和均为 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
  • 第一行包含 N,花的种类数量, K,花坛中可种植的花卉种类的最大数量,以及 M,比赛次数,以空格分隔。
  • 第二行包含每朵花的美丽值 S_1, S_2, \ldots, S_N,以空格分隔。
  • 以下 M 行提供有关每场比赛的信息。
  • 的 (2 + j)第行包含左端点 L_j 和右端点 R_j 构成比赛参加条件的花数范围 j,以及奖品 P_j 参与时收到,以空格分隔。

输出

输出(所选花朵的美丽值之和)的最大值 + (参加的所有比赛的奖金总和)在一行中。


示例输入 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