E. 0/1 Yukxalta

Vaqt limiti: 2000 ms Xotira limiti: 256 mb

Sizda \(n\) ta buyum bor, har birining og'irligi \(w_i\) va qiymati \(v_i\). Yukxaltaning sig'imi \(W\). Yukxaltaga og'irliklari yig'indisi \(W\) dan oshmaydigan buyumlarni tanlab (har bir buyum yo olinadi, yo olinmaydi — takrorlab bo'lmaydi), tanlangan buyumlar qiymatining yig'indisini maksimal qiling.

Kiruvchi ma'lumotlar

Birinchi qatorda ikkita butun son \(n\) va \(W\) (\(1 \le n \le 2000\), \(1 \le W \le 10^9\)) beriladi. Keyingi \(n\) ta qatorning har birida ikkita butun son \(w_i, v_i\) (\(1 \le w_i \le 10^9\), \(1 \le v_i \le 60000\),  kafolatlanadiki \(v_1+\dots+v_n \le 60000\)) beriladi.

Chiquvchi ma'lumotlar

Yagona qatorda — maksimal mumkin bo'lgan qiymat yig'indisini chiqaring.

Misollar

1

4 8
2 3
3 4
4 5
5 6

10

2

2 1
5 100
3 50

0

3

3 100
10 5
20 8
30 12

25