모빌 만들기

야엔(Yaen)이라는 신비로운 행성이 있는데, 이 행성의 공간은 2차원이다. 이 행성에는 아름다운 돌이 많이 있고, 야엔 사람들은 그 돌을 모으는 것을 좋아한다. 그들은 돌을 집으로 가져와 멋진 모빌 작품을 만들어 2차원 거실을 장식한다.

이 2차원 세계에서 모빌은 다음과 같이 재귀적으로 정의된다.

• 실에 매달린 하나의 돌, 또는
• 길이가 1인 막대의 양 끝에 두 개의 하위 모빌이 달린 것. 막대는 두 하위 모빌의 무게 중심에서 실로 매달린다. 두 하위 모빌의 무게가 각각 $n$, $m$이고 무게 중심으로부터의 거리가 각각 $a$, $b$일 때, $n \times a = m \times b$가 성립한다.

예를 들어 무게가 1, 1, 2인 돌 세 개가 있다면, 가능한 모빌과 그 너비의 예는 다음과 같다.

돌들의 무게와 방의 너비가 주어질 때, 다음 두 조건을 모두 만족하는 가장 넓은 모빌을 설계하는 것이 목표이다.

• 모든 돌을 사용한다.
• 너비가 방의 너비보다 작다.

돌 자체의 너비는 무시한다.

어떤 경우에는 막대의 양 끝에 매달린 두 하위 모빌이 겹칠 수도 있다(그림 참고). 이런 모빌도 허용된다. 위 예의 너비는 (1/3) + 1 + (1/4)이다.

입력의 첫째 줄에는 데이터셋의 개수가 주어진다. 이어서 그 개수만큼 데이터셋이 주어진다. 각 데이터셋의 형식은 다음과 같다.

r
s
w1
.
.
.
ws

r은 방의 너비를 나타내는 십진 소수로 $0 < r < 10$을 만족한다. s는 돌의 개수로 $1 \le s \le 6$이라고 가정해도 된다. wi는 i번째 돌의 무게로 정수이며 $1 \le w_i \le 1000$이라고 가정해도 된다.

주어진 돌들로는 너비가 $r - 0.00001$과 $r + 0.00001$ 사이인 모빌을 만들 수 없다고 가정해도 된다.

각 데이터셋에 대해, 위에서 정의한 가장 넓은 모빌의 너비를 기약분수 p/q 형태로 한 줄에 출력한다. 여기서 q > 0이고 p와 q는 1보다 큰 공약수를 갖지 않는다(정수 k는 k/1로, 너비가 0인 경우는 0/1로 쓴다). 조건을 만족하는 모빌이 없으면 대신 -1을 출력한다. 출력 줄에는 공백 등 불필요한 문자가 포함되어서는 안 된다.