<PREV Problem:
NEXT>
Solved by 1147 users: ...
UserDateAttemptTimeCMSC
Nakilon08 jan 2010Ruby700.0279 
Nakilon08 jan 2010Ruby400.0281 
Nakilon08 jan 2010Ruby500.0281 
Nakilon07 jan 2010Ruby300.0283 
kronos13 sep 2009Ruby500.0285 
turb003 aug 2008C++100.0188 
Madiyar_Tktl07 dec 2007C++1600.0188 
Madiyar_Tktl07 dec 2007C++1700.0188 
kronos25 sep 2007Ruby400.0288 
yinger65015 nov 2009FPC100.0190 
Madiyar_Tktl07 dec 2007C++1400.0190 
Nakilon07 jan 2010Ruby200.0290 
toshiba208 nov 2006FPC100.0191 
FD20 oct 2008FPC100.0191 
seshaoqistudent01 nov 2008FPC100.0191 
Madiyar_Tktl07 dec 2007C++1500.0192 
kronos25 sep 2007Ruby200.0292 
kronos25 sep 2007Ruby300.0292 
iputer02 feb 2008FPC100.0193 
denismr11 nov 2011Lua900.0194 
Madiyar_Tktl05 dec 2007C++1300.0194 
Languages
C++
544
FPC
278
C
194
Java
80
Kylix
51
Ruby
10
Python
3
Lua
2
Scheme
2
Perl
2
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 
 > 

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 170ms

SW soft NIX
ID = 107.23.129.77