P5052 [COCI 2017/2018 #7] Go

Branimirko 是世界著名游戏 Pokémon Go 的一位热情玩家。最近，他决定组织一场抓小精灵的比赛。比赛将在 Zagreb 的 Ilica 大街举行，主要赞助商是他的朋友 Slavko。奖励当然是糖果! 我们都知道，Ilica 是 Zagreb 最长的街道。在街道的同一侧有 $N$ 栋房子，房子从左到右分别依次有 $1$ 到 $N$ 的门牌号。 比赛前，Branimirko 看了看地图，发现了一共有 $M$ 只小精灵。每个小精灵都位于自己的各不相同的房子里，第 $i$ 个房子门牌号为 $A_i$，小精灵价值 $B_i$ 个糖果，并且只能在 $T_i$ 秒内被抓，之后它就会从地图上消失。 Branimirko 第 $1$ 秒在门牌号为 $K$ 的房子。接下来每一秒它可以移动到门牌号相邻的房子，或者不移动。当他在一个时刻和一只小精灵处在相同的房子时，他就会抓住这只小精灵，获得其对应的糖果，且这只小精灵就从地图上消失了。 因为 Branimirko 真的很喜欢糖果，所以他请求你的帮助。 帮助他求出他可以得到多少糖果。

输入的第一行包含三个整数 $N,K$（$1\le K\le N\le 10^3$）和 $M$（$1\le M\le 100$），代表房子数目，比赛开始的房子门牌号和小精灵的数量。 接下来的 $M$ 行每一行都包含三个整数 $A_i$（$1\le A_i\le N$），$B_i$（$1\le B_i\le 100$）和 $T_i$（$1\le T_i\le 2000$）。在输入数据中，小精灵始终按照房间号 $A_i$ 严格升序给出。

输出可获取的最大糖果数量。 ### 说明 在测试用例中，对于 $20\%$ 的数据，满足 $M\le 10$。 对于另外 $20\%$ 的数据，满足 $M\le 20$。 ### 样例 1 解释 一种策略是，Branimirko 首先在第 $3$ 个房子（$5$ 颗糖果）捕捉小精灵，然后分别在第 $7$ 个房子（$10$ 颗糖果）和第 $9$ 个房子（$100$ 颗糖果），总共 $115$ 颗糖果。 注意到 Branimirko 无法在 $1$ 号房子里抓住小精灵，因为他无法从他的起始位置（$5$ 号房子）及时到达这里。

In test cases worth 20% of total points, it will hold M ≤ 10. In additional 20% of total points, it will hold M ≤ 20. **Clarification of the first test case:** One strategy is that Branimirko first catches the Pokémon at house number 3 (5 candy), then, respectively, house numbers 7 (10 candy) and 9 (100 candy) for a total of 115 candy. Notice that Branimirko can’t catch the Pokémon at house number 1, because he can’t reach it in time from his starting position (house number 5).