Codah ClubVježbaj. Pošalji. Napreduj.
Prijavi se
Hrvatski
#00005E

z-most

Mr. Little Z went on a trip with several of his friends. However, when they walked through a bewitched forest they ended up at a bewitched bridge. If the total weight of everybody on the bridge is greater than the bridge's capacity, then the bridge teleports everything that is on it to "dimension X". More friends can start crossing the bridge at the same time (as a group), but the next group can only start to cross when the last friend from the previous group has finished crossing the bridge.


Because Mr. Little Z and his friends are in a hurry, they have asked you to
compute the minimum time needed for everyone to cross the bridge.


Mr. Little Z gave you the following information.
- Capacity of the bridge N (0 <= N <= 400 )
- Number of friends M, including Mr. Little Z ( 1 <= M <= 16 )
- For every friend Timei and Weighti , two integers that represent the
time that the i-th friend needs to cross the bridge and their weight
(1 <= Timei , Weighti <= 100).


InputThe input is read from the standard input. The first line contains the two integers N and M.
The next M lines contain the numbers Timei and Weighti .

OutputTo the standard output, output one integer, which represents the time that the friends
need to cross the bridge.

Input:
100 3
24 60
10 40
18 50
Output:
42
Explanation:
First, friends 2 and 3 go together, and after friend 3 crosses the bridge (after 18 seconds), friend 1 starts crossing.This gives a total of 18 + 24 = 42 seconds.

Submit solution

Coming later

The grading service will be connected in a later migration step. You can inspect the task and your previous results now.