#1044. mm和tt吃糖果

mm和tt来到渡渡鸟王国旅行，渡渡鸟王国是一片 $n \times n$ 块格子的花园，每块格子有一个坐标，左上角为入口 $(1,\ 1)$ ，右下角为出口 $(n,\ n)$ 。

花园的k个格子上有一定数量的糖果，作为两枚吃货，mm和tt致力于收集尽可能多的糖果。

两人初始是在入口为 $(1,\ 1)$ ，由于旅行时间紧张，两人只能向目的地方向行走（即向右走或向下走）；另外，为了防止花园地面塌陷，tt决定等mm先行到达出口再从入口出发。

mm和tt每到达一个有糖果的格子，便会拿走格子上的糖果，当然，对于同一个格子，mm拿走了格子上的糖果，tt再到达时便没有糖果可拿了。作为好朋友，mm和tt会将拿到的糖果一起分享，她们想知道如何走才能使拿到的糖果数之和最大。

第一行两个整数 $n,\ k$ 。

接下来 $k$ 行，每行三个正整数 $x_i,\ y_i,\ s_i$ ，表示在 $(x_i,\ y_i)$ 处有 $s_i$ 颗糖果。

保证对于任意的 $i \ne j$ 不存在 $x_i = x_j$ 且 $y_i = y_j$ 。

输出一行一个整数，表示mm和tt能获得的最大糖果总数。

样例输入

8 8
2 3 13
2 6 6
3 5 7
4 4 14
5 2 21
5 6 4
6 3 15
7 2 14

样例输出

67

$1 \le n \le 20$

$0 \le k \le n^2$

$1 \le x_i,\ y_i \le n$

$1 \le s_i \le 10^5$