分数: 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