Roger has a lot of work to do for DMOJ, but he also needs to study for CCO!
Roger has decided to outsource some of his additional DMOJ work to Tudor. Tudor is unwilling to do the work for free though, so to boost his salary, he requests that Roger pay him for every task he is outsourcing. It takes Roger exactly one week to figure out all the tasks he wants to outsource to Tudor.
Roger's tasks have the interesting property that they must be completed in the order they are being outsourced to Tudor. Furthermore, each task will take Tudor exactly two weeks to do. In the first week, Tudor will do some preparation work, and he will charge Roger a reading fee for the preparation work. In the second week, Tudor will actually complete the task, and charge a resolving fee. Due to the nature of the work, for any given task, these two weeks must follow one immediately after the other, with no gap in between.
Roger must commit to paying these fees in a timely manner. Roger doesn't have very much money - every week, he can only afford to give Tudor at most ~M~ dollars. Roger's bank, to avoid fraud, will not permit Roger to withdraw more than ~M~ dollars, and because of how unsafe Canada is, Roger will withdraw the exact amount of money needed to pay Tudor in a week. Roger must pay Tudor for exactly the work he will do in a week, otherwise Tudor will refuse.
Roger needs the tasks completed as soon as possible. What is the minimum time until Tudor can finish all tasks?
~1 \le N \le 300~
~1 \le M \le 10^3~
The first line will contain two integers, ~M~ and ~N~.
Each of the next ~N~ lines contains two integers, the reading fee and the resolving fee for each task. The tasks are presented in the order they must be completed.
Output a single integer, the minimum number of weeks needed for Tudor to do all of Roger's tasks.
100 5 40 20 60 20 30 50 30 50 40 40