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.

The number of students taking the van varies day to day, but you can assume that there will be no more than 500 students who will need to be transported home per day, since there are at most 500 students in the district. When students get out of class, they congregate at the high school bus stop. 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, because families from one home all take the trip home together. The bus has a limit of 40 students that it can hold at one time, so groups of students can only be allowed on as long as the total number of students doesn’t surpass 40. You can assume that no family will have more than 40 students. When the bus no longer has the space to take on more groups of students without surpassing its capacity, it will leave on a trip and drop off its current students at home, before returning to the bus stop. Thus, the bus will have to make many trips, to many different locations, to transport all of the children home.

The school district is in a city, and they have decided to measure distances based on city blocks, which are all the same length. You only need to determine the number of blocks that the bus has traveled on a given day. The city blocks are easily represented by an X-Y grid, where the bus stop is located at (0,0). Locations of students’ homes are given in (X,Y) coordinate pairs. Determining the number of blocks traveled is equivalent to determining the number of “moves” taken by the bus, since the x-y grid lines represent streets and the bus can only travel on the street lines, vertically or horizontally. One square represents one move, i.e. “moving” from (0,0) to (0,1) is equivalent to the bus traveling one block north. After dropping off the last student(s), the bus travels back to the bus stop at (0,0). If two groups of students live near the same intersection (for instance, both live off the intersection at (3,1)), then their coordinates will be the same, meaning that the number of moves or blocks between them is 0, and that transition does not add any gas mileage to the total.

Given a sequence of groups of students, your goal is to determine the minimum distance traveled by the bus in order to take all the students home.

Input

The input might consist of multiple datasets, each associated with one day of travel. The first line of the input is the number of datasets. This is followed by a blank line, before the start of the dataset. If there are multiple datasets, they are separate by blank lines. Each dataset has the following input format: First line of dataset: positive integer $L$, where $0 \leq L \leq 40$, which is the maximum capacity of the bus Second line of dataset: positive integer $F$, $0 \leq F \leq 500$, which is the number of families of students that need to go home on the bus The next $F$ lines of the dataset: each line contains 3 numbers for that family, in this order: the x-coordinate, the y-coordinate, and the number of students in that family. The order of these F lines is the order that the families are waiting in line at the bus stop, when they are all together.

Output

For each dataset, print one line containing a single integer that is the number of blocks/moves traveled that day. If there are multiple datasets, print a blank line between each dataset.

1

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

14