Нийт N ширхэг эд зүйлс байна. Эд зүйл бүрийг 1, 2, …, N гэж дугаарласан.

Эд зүйл i (1 ≤ i ≤ N) бүр дараах хоёр шинжтэй:

Жин: wᵢ Үнэлгээ (value): vᵢ

Таро эдгээрээс заримыг нь сонгон авч, үүргэвчиндээ хийхээр шийджээ.

Гэхдээ:

Үүргэвчийн даац нь W Сонгосон эд зүйлсийн нийт жин ≤ W байх ёстой Зорилго

Сонгож болох эд зүйлсийн үнэлгээний нийлбэрийг хамгийн их байхаар ол.

Оролтын файлын формат:

Стандарт оролтоос дараах хэлбэрээр өгөгдөнө:

N W
w₁ v₁
w₂ v₂
...
wₙ vₙ
​

Гаралтын файлын формат

Тарогийн авч болох хамгийн их нийт үнэлгээг хэвлэ.

Хязгаарлалтууд

• Бүх оролт нь бүхэл тоо
• 1 ≤ N ≤ 100
• 1 ≤ W ≤ 100000
• 1 ≤ wᵢ ≤ W
• 1 ≤ vᵢ ≤ 10⁹

Дэд бодлого

Жишээ тест

Оролот - 1

3 8
3 30
4 50
5 60

Гаралт - 1

90

Оролот - 2

5 5
1 1000000000
1 1000000000
1 1000000000
1 1000000000
1 1000000000

Гаралт - 2

5000000000

Оролот - 3

6 15
6 5
5 6
6 4
6 6
3 5
7 2

Гаралт - 3

17