← 返回题目列表

AtCoder · oupc2023_day1_h

H. 精彩舞台

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

配点 : 100 点

問題文

KowerKoint 你喜欢音乐游戏。 KowerKoint 在这个游戏的某首歌曲中,你可以轻松地 我们希望获得 X 的分数。

在这首歌中 M 节奏图标将会流动。 KowerKoint 您可以选择每个节奏图标 您最多可以点击 1 次。歌曲开头的乐谱是 0 在, i 个节奏图标时, 您可以获得 S_i 的分数。

另外, 1 \leq j \leq K , 您可以获得 a_j 起 件数最多为 b_j 为止的所有节奏图标的难度为 c_j 。

准确得分 X 只是 X 如果可能,找到您需要达到的最小可能最大难度。然而,任何 j 关于 a_j 起 件数最多为 b_j 只需添加总分即可,无需点击任何节奏图标即可 X ,最大难度为 0 。

制約

  • 1 \leq X \leq 10{,}000
  • 1 \leq M \leq 1{,}000
  • 1 \leq K \leq \min(200{,}000,\frac{M(M+1)}{2})
  • 1 \leq S_i \leq 10^{9}
  • 1 \leq a_j \leq b_j \leq M
  • (a_1,b_1),(a_2,b_2),\dots,(a_K,b_K) 不同
  • 1 \leq c_i \leq 10^{9}
  • 所有输入均为整数

小課題

  1. ( 1 点) a_j=b_j

  2. ( 99 点)无附加约束 打印第


入力

输入是按以下格式从标准输入给出的。

X M K
S_1 S_2 \dots S_M
a_1 b_1 c_1
a_2 b_2 c_2
\vdots
a_K b_K c_K

出力

准确得分 X 如果可能,找到需要达到的最大难度的最小可能值。 请输出 1 行。只是得分 如果你做不到 X 最好点击 -1 请输出。


入力例 1

7 4 3
3 2 2 3
1 2 10
2 3 3
3 4 20

出力例 1

10

4 以外的节奏图标。

这个测试用例不满足小题 1 的否定条件。


入力例 2

9 4 3
3 2 2 3
1 2 10
2 3 3
3 4 20

出力例 2

-1

准确得分 9 。

这个测试用例不满足小题 1 的否定条件。


入力例 3

7 4 3
3 2 2 3
1 1 10
2 2 3
3 3 20

出力例 3

20

这个测试用例满足小题 1 的否定条件。