<PREV Problem:
NEXT>
Solved by 1147 users: ...
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 
 < 

CD

Time limit = 5 second(s)

Memory limit = 33000 Kb

You have a long drive by car ahead. You have a tape recorder, but unfortunately your best music is on CDs. You need to have it on tapes so the problem to solve is: you have a tape N minutes long. How to choose tracks from CD to get most out of tape space and have as short unused space as possible.

Assumptions:

Input Value N, number of tracks and durations of the tracks.

For example, in the first sample input we have: N=5, number of tracks=3, first track lasts for 1 minute, second one 3 minutes, next one 4 minutes.

Output Maximum sum of duration times.

Input#1
5 3 
1 3 4
Output#1
5

Input#2
10 4
9 8 4 2

Output#2
10

Input#3
20 4 
10 5 7 4

Output#3
19

Input#4
90 8
10 23 1 2 3 4 5 7

Output#4
55

Input#5
45 8
4 10 44 43 12 9 8 2

Output#5
45

Author:

<PREV | Problem set | Search related messages | NEXT>


© acm.mipt DevGroup
The page was generated in 200ms

SW soft NIX
ID = 54.80.60.91