本题没有可用的提交语言。

描述

背景

汉森船长想要驾驶他的小驳船从汉堡沿易北河顺流而下前往库克斯港。在这次航行中，他必须考虑潮汐因素。当潮水回落时，水会流向北海，从而使船加速。当潮水上涨时，潮水的流向会降低船的实际速度。潮水的流速不是恒定的，而是随时间变化的。现在汉森船长想知道，为了使航行时间最短，他应该在什么时候出发。

当然，有截止时间需要遵守，而且汉森经营的是 “准时” 服务，所以到达时间应该尽可能晚，但不能晚于给定的截止时间。

问题

创建一个程序，计算出最优的出发时间 $t$。最优时间取决于两个标准：在 $t$时刻出发要保证汉森能在给定的截止时间之前到达库克斯港（即，到达时间 < 截止时间）。对于出发时间 $t$，航行时间是最短的。如果存在多个这样的出发时间，汉森会选择能让他到达库克斯港的最晚的那个时间。汉堡和库克斯港之间的距离是 $100$千米。船在水中（无水流影响时）以恒定速度 $10$千米 / 小时移动。实际速度（对地速度）是通过加上或减去水流速度来计算的。在任何时候，整条河上的水流速度和方向都是相同的。速度和方向每分钟最多改变一次，并且在下次改变之前保持不变。

输入

第一行包含测试用例的数量。

对于每个测试用例，你会得到最晚可能到达的时间 $d$。为了方便，这个时间是以从午夜开始的分钟数给出$（300≤d≤1440）$。然后给出包含水流数据的数据集数量 $（1≤d≤100）$。

一个水流数据集的形式为 “ms”，其中 m和s是整数。值$m$指定从该分钟开始给定的速度和方向有效， s给出新的潮汐速度和方向$（0≤m≤10000，−10≤s≤10）$。 s的正值表示从汉堡到库克斯港的水流方向，负值表示相反方向的水流。 时间值仅以分钟为单位给出，速度以千米 / 小时为单位，距离以千米为单位。你可以假设存在解决方案，并且数据集从时间 0的条目开始，指定出发时的初始水流速度。

输出

对于每个测试用例，打印一行，包含最优的出发时间。 你可以假设在那一天存在解决方案，也就是说，当在那天的午夜出发时，可以满足最晚到达时间。

输入数据 1

1

900

4

0 -3

60 0

90 2

150 4

输出数据 1

471