배의 항해

한센 선장은 작은 거룻배를 몰고 엘베강을 따라 함부르크에서 하류의 쿡스하펜까지 내려가려 한다. 항해 중에는 조수를 고려해야 한다. 썰물일 때는 물이 북해 쪽으로 흘러 배의 속도를 높여 주고, 밀물일 때는 조류가 배를 밀어내어 실제 속도를 늦춘다. 이 조류의 세기와 방향은 시간에 따라 변한다.

함부르크에서 쿡스하펜까지의 거리는 $100$ km이다. 배는 물에 대해 항상 일정하게 $10$ km/h로 나아간다(조류를 무시했을 때). 지면 기준 실제 속도는 여기에 조류 속도를 더해 구하며, $v = 10 + s$이다. 여기서 $s$는 현재 조류의 속도(km/h)이다. $s$가 양수이면 함부르크에서 쿡스하펜 방향의 조류로 배를 가속하고, 음수이면 반대 방향의 조류로 배를 감속한다. 조류의 크기는 배 자체 속도를 넘지 않으므로($-10 \le s \le 10$), 실제 속도는 결코 음수가 되지 않으며 최악의 경우에도 배는 제자리에 멈출 뿐이다. 조류는 어느 순간이든 강 전체에서 동일하고, 1분에 최대 한 번만 바뀌며 다음 변화 전까지 일정하게 유지된다.

한센은 적시(just-in-time) 운송을 하므로 안전한 한도 안에서 되도록 늦게 출발하려 한다. 자정을 기준으로 분 단위로 측정한 최적 출발 시각 $t$를 구하라. 최적 출발 시각은 다음 조건을 순서대로 만족한다.

1. $t$에 출발하면 마감 시각보다 반드시 이전에(엄밀히 이전에) 쿡스하펜에 도착한다.
2. 그런 출발 시각들 중에서 항해에 걸리는 시간이 가장 짧다.
3. 최소 항해 시간을 만드는 출발 시각이 여러 개이면, 그중 가장 늦은 것을 택한다.

첫 줄에 시나리오의 수 $T$가 주어진다.

각 시나리오는 다음과 같이 주어진다.

• 한 줄에 마감 시각 $D$ — 허용되는 가장 늦은 도착 시각으로, 자정부터의 분 단위이다($300 \le D \le 1440$).
• 한 줄에 조류 데이터 집합의 개수 $k$가 주어진다($1 \le k \le 100$).
• 이어서 $k$개의 줄에 각각 m s 형태로 두 정수가 주어진다($0 \le m \le 10000$, $-10 \le s \le 10$). $m$분부터 조류의 속도와 방향이 $s$ km/h가 되며, 다음 데이터 집합 전까지 이 값이 유지된다. $s$가 양수이면 함부르크에서 쿡스하펜 방향, 음수이면 반대 방향의 조류이다.

시간은 분, 속도는 km/h, 거리는 km 단위이다. 각 시나리오의 첫 데이터 집합은 $0$분에 대한 것이다. 유효한 출발 시각은 항상 존재한다고 가정해도 된다 — 자정에 출발하면 이미 마감 시각을 지킬 수 있다.

각 시나리오마다 최적 출발 시각(자정부터의 정수 분)을 한 줄에 출력한다.