Лимит времени 1000/1000/4000/4000 мс. Лимит памяти 65000/65000/65000/65000 Кб.
Problem description
Farmer John is taking some of his cows to the movies! While his
truck has a limited capacity of C (100 <= C <= 5000) kilograms, he
wants to take the cows that, in aggregate, weigh as much as possible
without exceeding the limit C.
Given N (1 <= N <= 100) cows and their respective weights W_i, determine
the weight of the heaviest group of cows that FJ can take to the
movies.
Input
* Line 1: Two space-separated integers: C and N
* Lines 2..N+1: Line i+1 contains a single integer: W_i
Output
* Line 1: A single integer that is the weight of the heaviest group of
cows that can go to the movies
Example
| stdin |
stdout |
259 5
81
58
42
33
61 |
242 |
81+58+42+61 = 242; this is the best possible sum Для отправки решений необходимо выполнить вход.
|