With the increasing popularity of smartphones, the demand for wireless networks is growing. A city has decided to provide wireless coverage in public places throughout the city.

Assume the city's layout is a grid formed by $129$ strictly parallel east-west streets and $129$ strictly parallel north-south streets, where the distance between adjacent parallel streets is a constant value of $1$. The east-west streets are numbered $0, 1, 2, \dots, 128$ from north to south, and the north-south streets are numbered $0, 1, 2, \dots, 128$ from west to east.

The intersections of east-west streets and north-south streets form junctions. The coordinate of the junction formed by the north-south street numbered $x$ and the east-west street numbered $y$ is $(x, y)$. Some junctions contain a certain number of public places.

Due to budget constraints, only one large wireless network transmitter can be installed. The coverage area of this transmitter is a square with a side length of $2d$ centered at the installation point. The coverage area includes the boundary of the square.

For example, the figure below shows the coverage area of a wireless network transmitter with $d = 1$.

Now, the relevant government department plans to install a wireless network transmitter with a propagation parameter $d$. They would like you to help them find a suitable junction in the city as the installation site to maximize the number of covered public places.

Input

The first line contains an integer $d$, representing the propagation distance of the wireless network transmitter.

The second line contains an integer $n$, representing the number of junctions with public places.

The next $n$ lines each contain three integers $x, y, k$, separated by spaces, representing the coordinates $(x, y)$ of the junction and the number of public places at that junction. Each coordinate is given only once.

Output

Output a single line containing two integers separated by a space, representing the number of installation site options that cover the maximum number of public places, and the maximum number of public places that can be covered.

Examples

Input 1

1
2
4 4 10
6 6 20

Output 1

1 30

Constraints

For $100\%$ of the data, $1 \leq d \leq 20$, $1 \leq n \leq 20$, $0 \leq x \leq 128$, $0 \leq y \leq 128$, $0 < k \leq 1\,000\,000$.