Branimirko 仍然是全球知名游戏 Pokémon Go 的狂热玩家。最近，他决定组织一场抓宝可梦的比赛。比赛将在萨格勒布的 Ilica 街举行，主要赞助商是他的朋友 Slavko。当然，奖品是糖果！

众所周知，Ilica 是萨格勒布最长的街道。街道的同一侧有 $N$ 栋房屋，每栋房屋的门牌号都在 $1$ 到 $N$ 之间。比赛从门牌号为 $K$ 的房屋开始。

在比赛开始前，Branimirko 看了看地图，发现了 $M$ 只宝可梦。每只宝可梦都位于一个（互不相同的）门牌号 $A_i$ 处，价值为 $B_i$ 个糖果，并且只能在接下来的 $T_i$ 秒内（即在时刻 $t < T_i$）被捕获，之后它就会从地图上消失，无法再被捕获。

Branimirko 每秒可以移动到相邻的门牌号（即从 $x$ 移动到 $x-1$ 或 $x+1$ 需要 $1$ 秒）。此外，当他捕获一只宝可梦时，该宝可梦就会从地图上消失。

由于 Branimirko 非常喜欢糖果，他向你寻求帮助。 请帮他确定他最多可以获得多少糖果！

输入格式

输入的第一行包含整数 $N, K$（$1 \le K \le N \le 1\,000$）和 $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 2\,000$），含义如题目所述。

在输入数据中，宝可梦的位置总是按照门牌号 $A_i$ 严格单调递增的顺序给出。

输出格式

输出 Branimirko 最多可以获得的糖果数量。

子任务

• 在占总分 20% 的测试数据中，满足 $M \le 10$。
• 在另外占总分 20% 的测试数据中，满足 $M \le 20$。

样例

输入样例 1

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

输出样例 1

115

输入样例 2

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

输出样例 2

172

说明

样例 1 说明

一种可行的策略是，Branimirko 首先捕获门牌号 3 处的宝可梦（获得 5 个糖果），然后依次捕获门牌号 7（获得 10 个糖果）和门牌号 9（获得 100 个糖果）处的宝可梦，总共获得 115 个糖果。

注意，Branimirko 无法捕获门牌号 1 处的宝可梦，因为他无法在规定时间内从起点（门牌号 5）赶到那里。