题目描述

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.

题目大意

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$ 号房子）及时到达这里。

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