【2012百度之星資格賽】J:百度的新大廈

<dl></dl>

<dt></dt>

時間限制: 

<dd></dd>

1000ms 

記憶體限制: 

65536kB

描述

繼百度搜尋框大廈之後，百度又于2012年初在深圳奠基了新的百度國際大廈，作為未來百度國際化的橋頭堡。不同于百度在北京的搜尋框大廈，新的百度國際大廈是一棟高樓，有非常多的樓層，讓每個樓中的電梯都能到達所有樓層将是一個極為不明智的設計。是以，設計師給出了一個特别的設計——一共大廈有m個電梯，每個電梯隻有兩個按鈕，（針對第i個電梯）兩個按鈕分别可以使電梯向上或ui層向下一定di層；百度國際大廈很高，你永遠到不了頂層，也就是說電梯沒有上限，但是，電梯不可以鑽入地下，也就是說是有下限的。我們将每層樓用整數标記，為了展現IT公司的特質，我們以0作為地面這一層的标記。

如果你某天在百度國際大廈的0層，僅可以選擇m個電梯中的一個乘坐（不可以中途換電梯），請你計算，你按電梯中的按鈕n次後（每次兩個按鈕選一個按），可以到達的最低樓層數。

輸入

輸入的第一行包括兩個整數，分别為n和m（1 ≤ n ≤ 1,000,000，1 ≤ m ≤ 2,000），表示按電梯按鈕的次數和大廈中的電梯數量。接下去的m行，每行包括2個由空格分割的數字，分别表示了提供的m個電梯中的某一個的上行按鈕上升一次的層數ui和下行按鈕下降一次的層數di（1 ≤ ui,di ≤ 1000）

輸出

輸出一個正整數，表示選用m個電梯中的一個後，在電梯裡按電梯中的按鈕n次後（每次兩個按鈕選一個按），可以到達的最低樓層數。

樣例輸入

樣例輸出

提示

按鈕上的移動樓層數無法改變，比方說從8層向下9層是不可行的