Mobile Computing

There is a mysterious planet called Yaen, whose space is 2-dimensional. There are many beautiful stones on the planet, and the Yaen people love to collect them. They bring the stones back home and make nice mobile arts out of them to decorate their 2-dimensional living rooms.

In their 2-dimensional world, a mobile is defined recursively as follows:

• a stone hung by a string, or
• a rod of length 1 with two sub-mobiles at both ends. The rod is hung by a string at the center of gravity of the two sub-mobiles. When the weights of the sub-mobiles are $n$ and $m$ and their distances from the center of gravity are $a$ and $b$ respectively, the equation $n \times a = m \times b$ holds.

For example, if you have three stones with weights 1, 1, and 2, here are some possible mobiles and their widths:

Given the weights of the stones and the width of the room, your task is to design the widest possible mobile satisfying both of the following conditions.

• It uses all the stones.
• Its width is less than the width of the room.

You should ignore the widths of the stones.

In some cases the two sub-mobiles hung from both ends of a rod might overlap (see the figure). Such mobiles are acceptable. The width of that example is (1/3) + 1 + (1/4).

The first line of the input gives the number of datasets. Then the specified number of datasets follow. A dataset has the following format.

r
s
w1
.
.
.
ws

r is a decimal fraction representing the width of the room, and satisfies $0 < r < 10$. s is the number of stones, and you may assume $1 \le s \le 6$. wi is the weight of the i-th stone, which is an integer, and you may assume $1 \le w_i \le 1000$.

You can assume that no mobile whose width is between $r - 0.00001$ and $r + 0.00001$ can be made from the given stones.

For each dataset, output one line containing the width of the widest possible mobile as defined above, given as a reduced fraction p/q where q > 0 and p and q have no common factor greater than 1 (write a whole number k as k/1, and write width zero as 0/1). If there is no mobile that satisfies the requirement, output -1 instead. The output line should not contain any extra characters such as spaces.