URI Online Judge | 1502

Corridor Crossing

By VC++, Colégio Etapa BR Brazil

Timelimit: 7

Twilight and her friends are trying to stop Discord from creating chaos. While they were walking through a very long corridor on their way to Canterlot, they ran into a deathly laser maze that blocked their way!

The corridor has width W. The laser maze consists of N wards powered with some non-negative energy Pi. Each ward is capable of creating a square of deathly lasers centered at the ward, with length equal to twice the square of its energy, and a pair of sides parallel to the walls of the corridor. Note that squares can overlap each other, and that there can be more than one ward at a single position.

Twilight plans to use her magic to change the wards’ energy to some non- negative integers so that it becomes possible to safely reach the other side of the corridor and continue their journey without being noticed. Turning off every ward could look suspicious, so Twilight decided to modify each ward’s energy so that the crossing is possible and the absolute difference of the total energy of the system before and after the crossing is minimal.

Since changing the energies of the wards while her friends are crossing might be dangerous, Twilight decides to make every modification beforehand, and she will not make any other changes during or after the crossing, as they don’t have much time left.

Help Twilight to complete her quest by finding the minimum possible absolute difference of the sum of the energies of the starting and ending configurations of the maze.

Input

The input contains many test cases. Each test case starts with a line containing two integers W and N (1 ≤ W ≤ 1000, 1 ≤ N ≤ 15). Following this are N lines, each containing three integers Xi, Yi and Pi, describing the position and initial energy of each ward (0 ≤ XiW, 0 ≤ Yi ≤ 1000, 0 ≤ Pi. The walls of the corridor are located at x = 0 and x = W. The last test case is followed by a line containing two zeroes.

Output

For each test case, print a single line containing the minimum possible absolute difference between the sum of the energies of the starting and ending positions of the maze.

Sample Input Sample Output

2 2
0 0 1
2 1 1
6 3
1 2 2
3 4 2
5 1 2
0 0

1
3