ICPC SWERC 2017 F - Shattered Cake

View as PDF

Submit solution

Points: 5
Time limit: 6.0s
Memory limit: 1G

Problem type

A rectangular cake is transported via a truck to a restaurant. On the way to the destination, the truck hits a pothole, which shatters the cake in N perfectly rectangular pieces of width w_i and length l_i, for 1 \le i \le N.

At the destination, the damage is assessed, and the customer decides to order a replacement cake of the same dimensions. Unfortunately, the original order form was incompletely filled and only the width W of the cake is known. The restaurant asks for your help to find out the length L of the cake. Fortunately, all pieces of the shattered cake have been kept.

Input Specification

The input consists of the following integers:

  • on the first line, the width W of the cake;
  • on the second line, the number N of shattered pieces;
  • on each of the next N lines, the width w_i and length l_i of each piece.

Constraints

1 \le N \le 5\,000\,000

1 \le W, L \le 10\,000

For each 1 \le i \le N, 1 \le w_i, l_i \le 10\,000.

Output Specification

The output should be the integer L.

Sample Input

4
7
2 3
1 4
1 2
1 2
2 2
2 2
2 1

Sample Output

6

Comments

There are no comments at the moment.