Levi Squad

reborn The Tough Winter Spar, 20...
Limits 3s, 256 MB

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.

Input

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.

Constraints

  • $1 \leq n \leq 10^3$.

  • $1 \leq k \leq 10^4$.

  • $1 \leq t \leq 10^6$.

  • $0 < x, y \leq 10^9$.

Output

Print the maximum possible sum of strength of deceased titans.

Sample

InputOutput
3 4
2 3 4
2 4 8
2 5 5
3 1 1
18

One of the ways to kill all the titans:

  • Soldier-1 attacks titan on (2, 3)
  • Soldier-2 attacks titan on (3, 1)
  • Soldier-3 attacks titans on (2, 4) and (2, 5)

Submit

Login to submit.

Statistics

75% Solution Ratio
tmwilliamlin168Earliest, Dec '19
NirjhorFastest, 0.6s
AnachorLightest, 3.0 MB
NirjhorShortest, 2712B
Toph uses cookies. By continuing you agree to our Cookie Policy.