No tags yet

No tag edit access

time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: 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.

Volunteer number i can fill A

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: A_{i} and B_{i} (0 <= A_{i} <= 10, 1 <= B_{i} <= 4).

Next N lines contain two integers each: A

Print one integer T - the minimal number of minutes required to filling M balloons.

Input

10 3

4 4

3 4

2 3

4 4

3 4

2 3

Output

5

Author: | Andrew V. Lazarev |

Resource: | Saratov SU Contest: Golden Fall 2004 |

Date: | October 2, 2004 |

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Sep/21/2020 00:08:28 (i2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|