UVA1648 商业中心 Business Center

###### 问题描述： 你来到一幢有m部电梯的大厦，每部电梯中只有两个按钮，一个按钮能使电梯上升U层，另一个按钮能使电梯下降D层，电梯不能到达比底楼低的楼层，你从底楼出发，选择一部电梯，求不更换电梯，通过按n次按钮能到达的最低楼层(不包括底楼)，底楼记作0楼。

第一行读入n(1 n 1,000,000)与m(1 m 2,000)。 接下来每行读入Ui,Di(1 Ui,Di 1,000)。

输出一个数，即不更换电梯，通过按n次按钮能到达的最低楼层(不包括底楼)。