time limit per test: 0.25
memory limit per test: 65536
Due to the preparation to the wedding you have to fill up M balloons. There are N volunteers and one device for balloons filling up. Device can fill at most one balloon at a time. Each volunteer can continuously operate the device for 1 minute.
Volunteer number i can fill Ai balloons during one minute and then he or she must have at least Bi minutes of rest.
You are to write a program that computes minimal possible time of filling up M balloons.
There are two integers M and N on the first line (1 <= M <= 100, 1 <= N <= 10).
Next N lines contain two integers each: Ai and Bi (0 <= Ai <= 10, 1 <= Bi <= 4).
Print one integer T - the minimal number of minutes required to filling M balloons.
|Author:||Andrew V. Lazarev
|Resource:||Saratov SU Contest: Golden Fall 2004
|Date:||October 2, 2004
|Server time: 2018-06-23 20:08:31||Online Contester Team © 2002 - 2016. All rights reserved.|