Ship Journey

Captain Hansen wants to sail his small barge down the river Elbe, from Hamburg to Cuxhaven. During the trip he must account for the tide. When the tide is falling, the water flows toward the North Sea and speeds the ship up; when the tide is rising, the drift works against the ship and slows it down. The drift is not constant — its speed and direction change over time.

The distance from Hamburg to Cuxhaven is $100$ km. Through the water the ship always moves at a constant $10$ km/h (ignoring drift). Its real speed over ground is that speed plus the drift: $v = 10 + s$, where $s$ is the current drift in km/h. A positive $s$ means drift from Hamburg toward Cuxhaven (which speeds the ship up); a negative $s$ means drift in the opposite direction (which slows it down). Because the drift never exceeds the ship's own speed ($-10 \le s \le 10$), the real speed is never negative — at worst the ship stands still. At any given moment the drift is the same everywhere on the river, and it changes at most once per minute, staying constant until the next change.

Hansen runs a just-in-time service, so he wants to leave as late as he safely can. Determine the optimal whole-minute departure time $t$ (measured in minutes from midnight). The optimal departure satisfies, in order:

1. Departing at $t$ guarantees arrival at Cuxhaven strictly before the deadline.
2. Among all such departures, the journey takes the least possible time.
3. If several departures achieve that minimal journey time, choose the latest one.

The first line contains the number of scenarios $T$.

Each scenario is given as follows:

• A line with the deadline $D$ — the latest allowed arrival time, in minutes from midnight ($300 \le D \le 1440$).
• A line with the number of drift data sets $k$ ($1 \le k \le 100$).
• $k$ lines, each of the form m s with two integers ($0 \le m \le 10000$, $-10 \le s \le 10$). From minute $m$ onward the drift speed and direction are $s$ km/h, and this value holds until the next data set. A positive $s$ is drift from Hamburg toward Cuxhaven; a negative $s$ is drift in the opposite direction.

Times are in minutes, speeds in km/h, distances in km. The first data set of every scenario is for minute $0$. You may assume a valid departure always exists — leaving at midnight already meets the deadline.

For each scenario, print a single line with the optimal departure time (a whole number of minutes from midnight).