Titans have breached Wall Maria! Since Erwin is in the capital, Levi quickly gathered his squad of $n$ members and ran to battlefield. But they encountered some difficulties on the way too and started to run out of resources. Reaching Wall Rose, they saw $k$ titans coming their way. The battlefield can be represented as a infinite grid and in each of the cells at most 1 titan is located.
The soldiers are well trained and can take out even 2 titans at a single attack if those titans share a side in the grid. However, as they are low on gas for their gear, each of the soldiers can make 1 attack at most.
Levi knows that his squad probably can't kill all the titans for now. But he wants to maximize the damage to be done. Simply, Levi wants his troop to attack in a way so that the summation of deceased titans' strength becomes maximum.
First line contains $n$ and $k$, the number of members in Levi Squad (including Levi himself) and the number of marked titans respectively.
$k$ lines follow. Each line contains three integers $x, y, t$; $(x, y)$ is the location and $t$ is the strength of a titan.
$1 \leq n \leq 10^3$.
$1 \leq k \leq 10^4$.
$1 \leq t \leq 10^6$.
$0 < x, y \leq 10^9$.
Print the maximum possible sum of strength of deceased titans.
| Input | Output |
|---|---|
3 4 2 3 4 2 4 8 2 5 5 3 1 1 | 18 |
One of the ways to kill all the titans:
| |