Maximum Catfish Capture

Bu Dengklek has a catfish pond which is structured as an $N\times N$ grid. The columns are numbered from $0$ to $N-1$ from west to east, and the rows are numbered from $0$ to $N-1$ from south to north. Each cell is denoted by $(c,r)$ for $0\le c,r\le N-1$.

There are $M$ catfish in the pond, each located in a distinct cell. For every $0\le i\le M-1$, the $i$-th catfish is in cell $(X_i,Y_i)$ and weighs $W_i$ grams.

Bu Dengklek plans to build vertical barriers (long-stakes) along some columns to catch the catfish. In column $c$, she may build a barrier of length $k$ (for any $1\le k\le N$), which covers the cells $(c,0), (c,1), \ldots, (c,k-1)$. She may also choose not to build a barrier in a column (which is considered as a barrier of length $0$).

A catfish in cell $(X_i,Y_i)$ is caught if and only if the following conditions hold:

• The cell $(X_i,Y_i)$ is not covered by a barrier in its own column (i.e. if the barrier in column $X_i$ has length $L_{X_i}$, then we require $L_{X_i}\le Y_i$).
• At least one of the two adjacent cells, namely $(X_i-1,Y_i)$ or $(X_i+1,Y_i)$ (if such a cell exists), is covered by a barrier. In other words, if $L_{X_i-1}$ or $L_{X_i+1}$ (when defined) is greater than $Y_i$, then the fish can be caught.

For convenience, denote the barrier length chosen for column $c$ as $L_c$ (with $L_c=0$ meaning no barrier is built). Then, for a fish in column $x$, we require:

• $L_x\le Y_i$, and
• If $x\not=0$ and $x\not=N-1$, then at least one of $L_{x-1}$ or $L_{x+1}$ is greater than $Y_i$. For the edge columns, only the existing neighbor is considered.

The total captured weight from column $x$ can be seen as the sum of weights of those fish that satisfy the condition. In fact, if we fix the barrier length in column $x$ to be $L_x$, and suppose its adjacent columns have barriers of lengths $L_{x-1}$ and $L_{x+1}$, then the effective height for capturing fish in column $x$ is $T_x=\max(L_{x-1},L_{x+1])$ (or just the adjacent column if at an edge). Thus, the fish in column $x$ that are captured are those located in rows in the interval $[L_x, T_x)$.

Your task is to choose the barrier lengths $L_0,L_1,\ldots,L_{N-1}$ (each in the range $0\le L_c\le N$, where a positive value indicates building a barrier) so that the total weight of the captured catfish is maximized. Finally, output this maximum total weight.

inputFormat

The first line contains two integers $N$ and $M$, where $N$ is the size of the pond and $M$ is the number of catfish.

Each of the following $M$ lines contains three integers: $X_i$, $Y_i$, and $W_i$, representing the column, row, and weight (in grams) of the $i$-th catfish respectively.

outputFormat

Output a single integer: the maximum total weight of the caught catfish.

sample

5 4
0 2 5
1 1 2
4 4 1
3 3 3

8