题目描述

$\red{Branimirko}$是一个对可爱精灵宝贝十分痴迷的玩家。

最近，他闲得没事组织了一场捉精灵的游戏。游戏在一条街道上举行，街道上一侧有一排房子，从左到右房子标号由$\red{1}$到$\red{n}$。

刚开始玩家在$\red{k}$号房子前。有$\red{m}$个精灵，第$\red{i}$只精灵在第$\red{A[i]}$栋房子前，分值是$\red{B[i]，}$以及它在$\red{T[i]}$秒内（含）存在，之后消失。

$\red{Branimirko}$可以选择移动至相邻的房子，耗时$\red{1}$秒。抓住精灵不需要时间，精灵被抓住后消失。时间从第$\red{1}$秒开始。$\red{Branimirko}$能最多获得多少 分值和。

输入格式

输入的第$\red{1}$行为三个正整数$\red{n，}$$\red{k，}$$\red{m}$。

接下来$\red{m}$行描述精灵的信息，分别为$\red{A[i]，}$$\red{B[i]，}$$\red{T[i]}$。

输出格式

输出$\red{Branimirko}$能最多获得多少分值和。

样例

输入样例

10 5 4

1 30 4

3 5 7

7 10 12

9 100 23

输出样例

115

提示

$\red{20\%}$的数据：$\red{m≤}$$\red{10}$

$\red{40\%}$的数据：$\red{m≤}$$\red{20}$

$\red{k≤}$$\red{n≤}$$\red{1000,m≤}$$\red{100,A[i] ≤}$$\red{N,B[i] ≤}$$\red{100,T[i] ≤}$$\red{2000，}$所有数为正整数。

很遗憾，它恰好不能抓住在一号房子前的精灵。 如果$\red{T[1]}$改成$\red{5，}$答案就是$\red{145}$