AT_oupc2023_day1_h.Wonderful Stage

通过率：0%

AC君温馨提醒

该题目为【atcoder】题库的题目，您提交的代码将被提交至atcoder进行远程评测，并由ACGO抓取测评结果后进行展示。由于远程测评的测评机由其他平台提供，我们无法保证该服务的稳定性，若提交后无反应，请等待一段时间后再进行重试。

题目描述

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
```
7 4 3
3 2 2 3
1 2 10
2 3 3
3 4 20
```
输出#1
```
10
```
输入#2
```
9 4 3
3 2 2 3
1 2 10
2 3 3
3 4 20
```
输出#2
```
-1
```
输入#3
```
7 4 3
3 2 2 3
1 1 10
2 2 3
3 3 20
```
输出#3
```
20
```

说明/提示

子任务

（ $1$ 分） $a_j=b_j$
（ $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 翻译

输入解题思路，AI测评打分。不知道怎么写?

首页