Problem F
School Bus

A school district is developing budgets for the upcoming school year and needs to know how much to allocate for transportation expenses, such as the cost of gas for taking kids home from school. Unfortunately, there is only one school van available for transportation. The school is taking information on the distance that the school van travels each day, in order to calculate the average cost of gas per day. You need to calculate that distance at the end of each day.

When students get out of class, they congregate at the high school bus stop in a neat line. The bus driver takes on students in groups based on their families. So if a student is an only child, they are allowed on the bus whenever there is capacity; if the student is from a family of $5$ children, then all $5$ children must be present at the bus stop before they are allowed on the bus. This decreases the number of redundant stops that the bus must make. The bus driver may choose how many groups to take before departing. However, it is of course unable to have more students in it than it has capacity for. When the bus departs, it will visit the homes of the students to drop them off in the same order as they showed up in the queue. When the bus has dropped off all of the students, it returns to the bus stop for the next batch. Thus, the bus will have to make many trips, to many different locations, to transport all of the children home.

Because the city’s mayor is very mathematically inclined, the city’s roads are reminiscent of the $x$-$y$ plane: on every integer point $(x,y)$, there is an intersection with roads leading to the $4$ intersections to the north, south, west and east. It thus follows that all roads have the same length. The bus stop is located at $(0,0)$. Every student specifies the location of their home by the $(x,y)$ intersection closest to it.

Now, the bus driver needs your help. He can currently see the queue, and wonders what the minimal number of road segments he needs to travel along to get all kids home. In particular, he can decide how many to bring on board the bus for each batch, and how to drive between the houses. However, he must be fair; the groups of students must board the bus in the same order as the queue, and they must be driven to their homes in the same order. Also note that at the end of the day, the bus must travel back to the bus stop at $(0,0)$.

Input

The first line of the input contains a single integer $t$ ($1 \leq t \leq 100$), the number of testcases. Then, the $t$ testcases follow.

The first line of each testcase contains the integer $C$ ($1 \leq C \leq 40$), the maximum capacity of the bus.

The second line contains the integer $F$ ($1 \leq F \leq 500$), the number of families of students that need to go home on the bus.

The following $F$ lines each describe a famliy. They each contain the integers $x$, $y$ and $a$ ($0 \leq x,y \leq 100$, $1 \leq a \leq C$), the coordinates of their house and the number of students in that family. The families are given in the order that they are waiting in line at the bus stop, when they are all together.

Output

For each each testcase, an integer: the number of roads traveled that day by the bus if the driver makes optimal decisions. Print each answer on its own line.

1
10
4
1 2 3
1 0 3
3 1 4
3 1 4

14