2023, група A, 10-12 клас
32
B.
ТЪРГОВЕЦ
186
Условие
ГРУПА A. ЗАДАЧА B. ТЪРГОВЕЦ
----
Имало едно време млад търговец на име Георги, който имал малък търговски бизнес. Един ден той решил да предприеме пътуване до далечна земя, за да купи някои редки стоки, които можел да продаде на висока цена в родния си град. Георги имал ограничени финансови средства и не можел да си позволи да купи всички стоки, които искал, но все пак искал да увеличи максимално печалбата си.
Докато пътувал из пазарите на далечната земя, той намерил много различни видове стоки, всяка със собствено тегло и стойност. Някои стоки били тежки и с висока стойност, докато други били леки, но с ниска стойност. Георги имал ограничено място в раницата си, така че не можел да купи всички стоки, които искал.
Помогнете на търговеца като напишете програма, която така да подбере стоките, с които Георги да напълни раницата си така, че печалбата му да е максимална.
От благодарност Георги ще Ви превърне в легенда в търговската общност, вдъхновявайки много други млади търговци да използват същия алгоритъм, за да вземат интелигентни и печеливши бизнес решения.
Вход:
От първия ред на стандартния вход се въвеждат две цели числа: n и c, разделени от интервал, които съответстват на броя на стоките и капацитета на раницата на търговеца.
На следващите n реда от стандартният вход се въвеждат по две цели числа: v и w, разделени от интервал, които съответстват на теглото и стойността на всяка стока.
Изход:
На един ред на стандартния изход програмата трябва да изведе максималната печалба, която търговеца може да получи за стоките в раницата си. Отговорът се извежда до третия знак след десетичната запетая.
Примерен вход:
5 15
3 50
5 70
2 30
1 10
4 40
Примерен изход:
200.000