펌프와 파이프

수백 년 동안 소방대는 불을 끄기 위해 물을 사용해 왔다. 그러나 불이 난 바로 그 자리에 항상 충분한 물이 있는 것은 아니어서, 소방대는 물을 필요한 곳까지 옮기기 위해 많은 펌프와 파이프를 갖추고 있다. 지켜야 할 물리적 제약이 여럿 있어서 펌프와 파이프로 이루어진 관로를 설치하는 일은 간단하지 않다.

물을 옮기는 데에는 한 종류의 파이프만 사용한다. 각 파이프는 지름이 75밀리미터, 길이가 20미터이다. 파이프로 흘려보내는 물의 유량에 따라 관로를 따라 압력이 손실된다. 미터당 압력 손실은 유량 $f$(분당 리터)에 따라 다음과 같다.

압력은 지형의 경사에도 영향을 받는다. 수직 거리 10미터마다 압력이 1바씩 변하며, 파이프가 오르막을 지나면 압력이 낮아지고 내리막을 지나면 높아진다.

펌프는 최소 2바의 입력 압력이 필요하며 항상 일정하게 8바의 출력 압력을 만들어 낸다. 다만 펌프를 압력을 낮추는 용도로 쓸 수는 없다. 파이프는 12바를 초과하는 압력을 견디지 못하고, 흐름을 일정하게 유지하려면 모든 지점에서 압력이 최소 2바 이상이어야 한다. 효과적인 소화를 위해 관로 끝에서의 압력은 최소 5바 이상, 최대 8바 이하여야 한다.

관로의 맨 앞(위치 0)에는 항상 펌프가 하나 있다. 그 밖의 펌프는 두 파이프가 맞닿는 지점에만 놓을 수 있으며, 관로의 끝에는 놓을 수 없다.

필요한 펌프의 최소 개수와 그 위치를 구하는 프로그램을 작성하여라. 최소 개수의 펌프를 쓰는 배치가 여러 개라면, 펌프가 관로의 앞쪽에 더 가깝게 놓이는 배치를 택한다(펌프를 멀리 나르는 일은 즐겁지 않다).

첫 줄에는 시나리오의 개수가 주어진다.

각 시나리오는 원하는 유량을 나타내는 정수 $f \in {200, 400, 600, 800, 1000, 1200}$(분당 리터)가 한 줄에 하나 주어지는 것으로 시작한다. 다음 줄에는 두 정수 $n$과 $m$이 공백 하나로 구분되어 주어진다. $1 \le n \le 20$은 사용할 파이프의 개수, $1 \le m \le 400$은 경사가 일정한 구간의 개수이다.

이어지는 $m$개의 줄은 각 구간을 설명하며, 두 정수 $l$과 $s$가 공백 하나로 구분되어 주어진다. $l > 0$은 구간의 길이(미터)이고, $s$는 백분율로 나타낸 경사이다($s = 10$은 길이 100미터당 10미터 상승, $s = -50$은 100미터당 50미터 하강을 뜻한다; $-100 \le s \le 100$).

$m$개 구간 길이의 합은 정확히 $n \times 20$미터임이 보장된다.

각 시나리오에 대해 먼저 Scenario #i: 형식의 줄을 출력한다. 여기서 $i$는 1부터 시작하는 시나리오 번호이다.

다음 줄에는, 조건을 만족하는 배치가 존재하면 펌프의 개수(맨 앞의 펌프 포함)를 출력하고 이어서 콜론과 공백 하나 : 를 출력한 뒤, 펌프의 위치들을 공백 없이 쉼표로 구분하여 출력한다. 펌프의 위치는 파이프 이음매의 번호로, 번호 0은 관로의 시작점이고 번호 $j$는 처음 $j$개의 파이프 바로 뒤 지점을 뜻한다. 펌프 개수가 최소인 모든 배치 중에서 위치들이 사전순으로 가장 앞서는 것을 출력한다(첫 번째 펌프 위치를 가능한 한 작게, 그다음 위치를 가능한 한 작게, … 정하면 된다). 조건을 만족하는 배치가 없으면 대신 no solution을 출력한다.

이어지는 시나리오 사이에는 빈 줄 하나를 넣어 구분한다.