Задача №112621. Пиратская шлюпка - 2
Пират нашел на захваченном корабле N драгоценных предметов, каждый из которых имеет некоторую стоимость ( V i для предмета с номером i ). Известен также вес каждого из предметов ( W i для предмета с номером i ). Во время боя захваченный корабль получил серьёзные повреждения и вот-вот затонет. Пират может увезти на шлюпке на свой корабль только C килограммов груза. Найдите наибольшую стоимость предметов, которые может увезти пират.
В первой входной строке записана грузоподъёмность шлюпки пирата в килограммах ( 1 ≤ C ≤ 5000 ). Во второй строке – количество предметов N ( 1 ≤ N ≤ 100 ). В следующих N строках записаны данные о предметах в формате
<вес> <стоимость>
Программа должна вывести одно число: наибольшую стоимость предметов, которые может увезти пират.
8 4 1 15 5 10 3 9 4 5
29