~/algor $ cat masalalar/dp-yukxalta
DP-03
Yukxalta
Muallif:
Iqbolshoh Ilhomjonov
O'rtacha
1000 ms
128 MB
66%
Xaltaga ko'pi bilan $W$ kg sig'adi. $n$ ta buyum bor: $i$-buyumning og'irligi $w_{i}$ kg, qiymati $v_{i}$. Buyumlarni bo'lib bo'lmaydi, har biri ko'pi bilan bir marta olinadi. Xaltadagi buyumlarning eng katta umumiy qiymatini toping.
Kiruvchi ma'lumotlar
Birinchi qatorda ikkita natural son: $n$ va $W$. Keyingi $n$ ta qatorning har birida ikkita natural son: $w_{i}$ va $v_{i}$.
Chiquvchi ma'lumotlar
Bitta butun son — eng katta umumiy qiymat.
Izoh
$1 \le n \le 100$
$1 \le W \le 10^{4}$
$1 \le w_{i} \le 10^{4}$
$1 \le v_{i} \le 10^{6}$
Misollar
Kirish #1
4 7 1 1 3 4 4 5 5 7
Chiqish #1
9
Kirish #2
2 3 5 10 4 20
Chiqish #2
0