马拉松比赛正在美丽的乡村进行规划。赛道将沿着一条漫长的双向道路设置。组织者希望确定比赛在道路上的具体位置，以最大限度地提升参赛者的体验，让他们尽可能多地欣赏美丽的风景，从而分散对疲惫肢体的注意力。风景的美丽程度取决于你在道路上的位置以及你奔跑的方向。因此，组织者允许参赛者进行最多两次掉头，只要道路的任何部分在每个方向上都不会被使用超过一次。

我们将长度为 $m$ 米的道路建模为一个 $2 \times m$ 的矩形网格，其中每个单元格都有一个非负的“美感”值。列代表道路从起点到终点的每一米。一列中的顶行表示向道路终点方向奔跑时该路段的美感，底行表示向道路起点方向奔跑时的美感。长度为 $x$ 的比赛即为网格中恰好 $x$ 个单元格的集合。这 $x$ 个单元格必须在网格中形成一条路径，且没有单元格被访问超过一次；我们只能从顶行的单元格向右或向下移动，只能从底行的单元格向左或向上移动。参见图 M.1 中的比赛示例。比赛的“总美感”是所包含单元格美感值的总和。

由于道路很长，与其提供所有 $2m$ 个美感值列表，不如将道路的每一侧划分为少量段，其中段内的单元格具有相同的恒定美感值（美感为 0 的单元格直接省略）。

图 M.1：样例输入 1 的说明。单元格中的数字表示道路每一米的美感值（省略的值为 0）。高亮显示的单元格和箭头标记了包含两次掉头的最优比赛路径。

输入格式

输入的第一行包含三个整数 $m, x$ 和 $n$ ($1 \le m \le 10^9, 1 \le x \le 2m, 0 \le n \le 200$)，分别表示道路长度、比赛长度和段数。

接下来是 $n$ 行，描述这些段。每行包含三个整数 $a, b, v$ ($0 \le a, b \le m, 1 \le v \le 10^9$ 且 $a \neq b$)，描述一个端点为 $a$ 和 $b$ 且美感值为 $v$ 的段。如果 $a < b$，则这是网格顶行范围 $[a, b)$ 内的单元格段；如果 $a > b$，则这是网格底行范围 $[b, a)$ 内的单元格段。

未被任何段覆盖的道路部分美感值为 0。网格中的每个单元格最多被覆盖一次（即在同一方向上没有重叠的段）。

输出格式

输出比赛可能获得的最大总美感。

样例

样例输入 1

19 14 6
14 5 7
11 15 6
3 7 4
16 15 5
19 17 8
0 3 9

样例输出 1

89

样例输入 2

100000 42195 2
30000 60000 500000000
40000 10000 1000000000

样例输出 2

35548500000000