Optimal Placement of a Wireless Network Transmitter

In a modern city where wireless connectivity is crucial, the government plans to install a single high-power wireless network transmitter. The city is laid out as a grid formed by 129 east-west streets and 129 north-south streets, with consecutive streets being exactly 1 unit apart. The east-west streets are numbered from 0 (north) to 128 (south) and the north-south streets from 0 (west) to 128 (east). The intersection of the north-south street numbered \( x \) and the east-west street numbered \( y \) is located at coordinates \( (x,y) \).

Some intersections hosts a number of public places. Due to limited funding, only one transmitter can be installed. The transmitter has a square broadcast range centered at its installation point with a side length of \( 2d \) (i.e. it covers all intersections \( (i,j) \) that satisfy \( |i-p| \le d \) and \( |j-q| \le d \), where \( (p,q) \) is the installation point). The boundaries of the square are included in the coverage.

Your task is to determine the optimal intersection to install the transmitter so that the total number of public places covered is maximized.

inputFormat

The input consists of:

1. A line containing two integers \( d \) and \( m \) where \( d \) (\( 0 \le d \le 128 \)) is the broadcast parameter and \( m \) is the number of intersections that have public places.
2. Then \( m \) lines follow. Each line contains three integers \( x \), \( y \), and \( c \). Here, \( (x, y) \) (with \( 0 \le x, y \le 128 \)) represents the coordinates of an intersection and \( c \) (a positive integer) represents the number of public places at that intersection.

outputFormat

Output a single integer representing the maximum total number of public places that can be covered by the transmitter when installed at an optimal intersection.

sample

1 3
0 0 5
1 1 10
2 2 3

18