AT_oupc2023_day1_h Wonderful Stage

KowerKoint 君很喜欢音乐游戏。他想在这个游戏中的某首曲目里，尽可能简单地获得恰好 $X$ 分。 这首曲目中有 $M$ 个节奏图标会依次出现。KowerKoint 君对每个节奏图标最多只能点击 $1$ 次。游戏开始时分数为 $0$，如果他点击第 $i$ 个节奏图标，将会获得 $S_i$ 分。 另外，对于 $1 \leq j \leq K$，若将第 $a_j$ 个到第 $b_j$ 个节奏图标全部点击，则该动作的难度为 $c_j$。 请判断是否存在一种点击方案，可以使得最终得分刚好为 $X$。如果存在，请求出为了达成该分数时所必须经历的最大难度中的最小可能值。如果可以通过不完整点击任意区间（即对于任意 $j$，从第 $a_j$ 到第 $b_j$ 的区间内存在没被点击的节奏图标）来获得恰好 $X$ 分，则最大难度视为 $0$。

输入通过标准输入给出，格式如下： > $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$ 分，请输出为达成该分数所需最大难度的最小可能值。如果无法获得恰好 $X$ 分，请输出 `-1`。

## 子任务 1. （$1$ 分）$a_j=b_j$ 2. （$99$ 分）无额外约束 ## 样例解释 1 点击除了第 $4$ 个以外的所有节奏图标是最优的。 本测试用例不满足子任务 1 的约束。 ## 样例解释 2 无法使得分数恰好为 $9$。 本测试用例不满足子任务 1 的约束。 ## 样例解释 3 本测试用例满足子任务 1 的约束。 # 数据范围 - $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$ - 所有输入均为整数。 由 ChatGPT 5 翻译