Free Pie Catcher

SERKOI recently launched a game called "Free Pie". The game is played on a stage consisting of \(w\) cells, numbered from 1 to \(w\) from left to right. A player stands on one of these cells with a tray. At the start, the player may choose any cell as the starting position.

After the game begins, pies drop vertically from the top of the stage. Each pie falls at a specified time \(t\) (in seconds) and from a given column \(x\). The player can move at most 2 cells per second in either direction (or remain stationary). If, at the moment a pie reaches the level of the player, the player is standing exactly in the corresponding column, then the pie is caught and its score \(s\) is added to the total.

Note that if more than one pie falls at exactly the same time and in the same cell, the player catches them all simultaneously. However, pies falling at the same time but in different cells cannot all be caught since the player can only be at one cell.

Your task is to compute the maximum total score the player can achieve by planning the movements optimally. Remember that the player may choose any starting position.

inputFormat

The first line contains two integers \(w\) and \(n\), where \(w\) (\(1 \leq w \leq 10^5\)) is the width of the stage and \(n\) (\(1 \leq n \leq 10^5\)) is the number of pies.

Each of the next \(n\) lines contains three integers \(t\), \(x\), and \(s\) (where \(1 \leq t \leq 10^9\), \(1 \leq x \leq w\), and \(1 \leq s \leq 10^4\)). Here, \(t\) denotes the time (in seconds) when a pie reaches the level of the player, \(x\) is the column from which the pie falls, and \(s\) is the score of that pie.

outputFormat

Output a single integer: the maximum total score that the player can achieve.

sample

5 3
2 3 5
3 4 7
4 3 10

22