Tasks:
 
Task DescriptionDiscussion (0)
Task :: 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).

INPUT:
The 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 .

OUTPUT:
To 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
:
:
Available Languages
Task info
Name:z-most
Time:1 sec.
Memory:16 MB
#Tests:15
Author:Z
AddedBy: admin
Task Ratings
Difficulty:

4.4 (17 votes)
Quality:

4.4 (15 votes)
Acceptance Rate
Recent Submissions
Fastest Solutions
UserTime
admin 0.007 s.
halil 0.008 s.
majce 0.01 s.
mirosl@v 0.01 s.
dejandenib 0.01 s.
a70babat 0.011 s.
crusader 0.012 s.
amirbehshad 0.013 s.
aleksa92 0.038 s.
Weramajstor 0.039 s.
Solved By