Oscar is the captain of his very own spaceship, which he has endearingly named Oscarella.

Oscar will be embarking on ~T~ missions to collect gems from planet Globgalab. On each mission he will attempt to get ~N~ gems (this quantity will vary between missions). To collect a gem, he must fly his ship directly over the gem and beam it up. Oscar wants to collect all the gems, but he also wants to minimize the distance he moves so that Oscarella can remain in pristine condition.

However, there is one other issue. Each gem has a weight of ~a_i~. The ship, Oscarella, has a certain power level that dictates what gem it can pick up. Specifically, if Oscarella has a power level of ~g~, it can only pick up a gem that weighs no more than ~floor(g/5)~ pounds.

(Note, the function ~floor(x)~ returns the greatest integer less than or equal to x.)

To aid him on his mission, Oscar can use the gems he has picked up to increase Oscarella's power level further. A gem with weight ~a_i~ will increase Oscarella's power level by ~a_i~. Oscar and his spaceship will start at ~(0, 0)~, can you help him find the minimum distance he must travel to get all ~N~ gems?

Input Specification

The first line contains a single integer ~T~, the number of missions per test case, ~(1 \le T \le 20)~

The inputs for the ~T~ missions follow.

The first line of each mission input contains two positive integers, ~g~ and ~N~, ~(1 \le g \le 1000)~, ~(1 \le N \le 18)~

Each of the next ~N~ lines each contain three integers, ~x~, ~y~ and ~m~, representing the (~x~, ~y~) position and weight of the gem, in pounds. ~(-10^5 \le x, y \le 10^5)~, ~(1 \le m \le 5000)~

No two gems will be at the same location.

Output Specification

For each input case, on a line by itself, output -1.0 if there is no way for Oscarella to beam up all the gems or the shortest distance it needs to travel to beam up all the gems otherwise.

Note, for all cases where Oscarella can beam up all the gems, any answer within an absolute or relative error of ~10^{-6}~ will be accepted.

Subtasks

Subtask 1 [60%]

~N \leq 10~

Subtask 2 [40%]

No additional constraints.

Sample Input

2
100 3
20 0 21
30 0 5
40 0 10
125 4
1 1 30
-1 1 4
-1 -1 6
1 -1 5

Sample Output

60.0
-1.0