[COCI2017-2018#7] Go

Branimirko是世界著名游戏Pokémon Go的一位热情玩家。最近，他决定组织一场抓小精灵的比赛。比赛将在Zagreb的Ilica大街举行，主要赞助商是他的朋友Slavko。奖励当然是糖果! 我们都知道，Ilica是Zagreb最长的街道。在街道的同一侧有N栋房子，每栋房子都有一个1到N之间的门牌号。比赛从K号房子开始。 比赛前，Branimirko看了看地图，发现了一共有M只小精灵。每个小精灵都位于自己的(各不相同的)房子里，房子门牌号为Ai，小精灵价值Bi个糖果，并且只能在Ti秒内被抓，之后它就会从地图上消失。 Branimirko每秒可以访问一个门牌号。而且，当他抓住一只小精灵时，那只小精灵就从地图上消失了。 因为Branimirko真的很喜欢糖果，所以他请求你的帮助。 帮助他求出他可以得到多少糖果! ### 输入输出格式 输入格式: 输入的第一行包含三个整数N,K(1≤K≤N≤1 000)和M(1≤M≤100)，代表房子数目,比赛开始的房子门牌号和小精灵的数量。 接下来的M行每一行都包含三个整数Ai（1≤Ai≤N），Bi（1≤Bi≤100）和Ti（1≤Ti≤2000）。在输入数据中，小精灵始终按照房间号Ai严格升序给出。 输出格式: 输出可获取的最大糖果数量。 ### 说明 在测试用例中，对于20%的数据,有M≤10。 对另外20%的数据,有M≤20。 第一个样例的说明: 一种策略是，Branimirko首先在第3个房子(5颗糖果)捕捉小精灵，然后分别在第7个房子(10颗糖果)和第9个房子(100颗糖果)，总共115颗糖果。 注意到Branimirko无法在1号房子里抓住小精灵，因为他无法从他的起始位置(5号房子)及时到达这里。

Branimirko is still a passionate player of the world-renowned game Pokémon Go. Recently, he decided to organize a competition in catching Pokémon. It will be held in Ilica street in Zagreb, and the main sponsor is his friend Slavko. The reward is, of course, candy! Ilica is, as we all know, the longest street in Zagreb. There are N houses on the same side of the street, and each house has a house number between 1 and N. The competition begins at house number K. Before the competition, Branimirko looked at the map and saw M Pokémon. Each Pokémon is located at its (distinct) house number Ai , is valued at Bi candy, and can be caught only in the next Ti seconds, after which it disappears from the map and is impossible to catch. Branimirko can visit one house number per second. Also, when he catches a Pokémon, that Pokémon disappears from the map. Since Branimirko really likes candy, he asked for your help. Help him and determine the maximal amount of candy he can get!

The first line of input contains integers N, K (1 ≤ K ≤ N ≤ 1 000) and M (1 ≤ M ≤ 100), the number of houses, the starting house number and the number of Pokémon. Each of the following M lines contains integers $A_i$ (1 ≤ $A_i$ ≤ N), $B_i$ (1 ≤ $B_i$ ≤ 100) and $T_i$ (1 ≤ $T_i$ ≤ 2 000) from the task. In the input data, the Pokémon will always be in a strictly ascending order by house number $A_i$ .

You must output the required maximal amount of candy from the task.

10 5 4
1 30 4
3 5 7
7 10 12
9 100 23

115 

20 8 7
1 35 14
4 57 1
6 32 2
9 94 28
14 78 8
15 8 1
17 55 3

172

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).