256. Balloons
time limit per test: 0.25
sec.
memory limit per test: 65536
KB
input: standard
output: standard
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 A_{i} balloons during one minute and then he or she must have at least B_{i} minutes of rest.
You are to write a program that computes minimal possible time of filling up M balloons.
Input
There are two integers M and N on the first line (1 <= M <= 100, 1 <= N <= 10).
Next N lines contain two integers each: A_{i} and B_{i} (0 <= A_{i} <= 10, 1 <= B_{i} <= 4).
Output
Print one integer T  the minimal number of minutes required to filling M balloons.
Sample test(s)
Input
10 3
4 4
3 4
2 3
Output
5
Author:  Andrew V. Lazarev

Resource:  Saratov SU Contest: Golden Fall 2004

Date:  October 2, 2004

Server time: 20180219 01:06:15  Online Contester Team © 2002  2016. All rights reserved. 

