Лепреконы в данной задаче появились по соображениям общей морали, так как грабить банки — нехорошо.
Вам удалось заключить неплохую сделку с лепреконами, поэтому они пустили вас в своё хранилище золотых слитков. Все слитки имеют единую пробу, то есть стоимость 1 грамма золота в двух разных слитках одинакова. В хранилище есть n слитков, вес i-го слитка равен wi кг. У вас есть рюкзак, вместимость которого M килограмм.
Выясните максимальную суммарную массу золотых слитков, которую вы сможете унести.
В первой строке дано число слитков —– натуральное число n (1 ≤ n ≤ 1000) и вместимость рюкзака –— целое число M (0 ≤ M ≤ 104). Во второй строке записано n натуральных чисел wi (1 ≤ wi ≤ 104) -— массы слитков.
Выведите единственное число — максимальную массу, которую можно забрать с собой.
|
5 15 3 8 1 2 5 |
15 |
|
5 19 10 10 7 7 4 |
18 |