Şerpanın Çantası

Lhakpa dağ bələdçisi və şerpadır. Onun qarşısında hər birinin müəyyən çəkisi və dəyəri olan bir neçə əşya var. Lhakpanın kürək çantası ən çox W vahid çəki daşıya bilir. O, çantasına elə əşyalar seçmək istəyir ki, ümumi çəki W-ni aşmasın və seçilmiş əşyaların ümumi dəyəri maksimum olsun.

Hər əşyadan ən çox bir dəfə istifadə etmək olar.

Giriş verilənləri

Birinci sətirdə iki tam ədəd n və W verilir — əşyaların sayı və çantanın maksimal daşıma gücü.

Növbəti n sətirin hər birində iki tam ədəd verilir — müvafiq əşyanın çəkisi və dəyəri.

Çıxış verilənləri

Çantaya yerləşdirilə biləcək əşyaların mümkün olan maksimum ümumi dəyərini çap edin.