1535: Orange

       国际网络警察公司新建了一个很高的商务中心作为它的总部并且租出部分空间换取利润。中心有很多层，如果给中心的m个电梯在每层分别放置按钮是不现实的。所以每个电梯在一层只有两个按钮，一个按钮在第i层使你上升Ui层，另一个按钮使你下降Di层。商务中心很高所以不用考虑层数的问题（你永远到不了最高层），但是你不能到地下去。所有楼层从0开始标号，0代表地面。

       你从地面开始，必须从m个电梯中选择一个乘坐。在这之后不能换电梯。问从地面恰好按过n次按钮后你最低能到达哪一层？

    输入数据的第一行包含一个整数t（t ≤ 50），代表测试数据的组数。

    对于每组测试数据的第一行包含两个整数n和m（1≤n≤1,000,000 1≤m≤2,000），分别代表按的次数和电梯的数目。接下来m行描述了每个电梯，每行有两个整数Ui和Di（1≤Ui,Di≤1,000）。

       输出一个正整数，即能到达的最低层数。

1
10 3
15 12
15 4
7 12

13