配点 : 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 点) a_j=b_j
-
( 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 的否定条件。