A Mộng làm bánh dorayaki. Cho n chiếc bánh dorayaki, chiếc thứ i có một giá trị nhất định. Hãy chọn ra một số chiếc bánh sao cho tổng giá trị là lớn nhất nhưng không được vượt quá giới hạn sức chứa W. Mỗi chiếc bánh chỉ được chọn một lần (bài toán cái túi 0-1).

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên n, W. Trong n dòng tiếp theo, mỗi dòng chứa hai số nguyên wᵢ, vᵢ.

Dữ liệu ra

In ra một số nguyên biểu thị tổng giá trị lớn nhất.

Ví dụ

Input

4 10
2 5
3 7
4 9
5 10

Output

16

Ghi chú

Giới hạn dữ liệu

n ≤ 100

1: Bài này kiểm tra quy hoạch động, là bài toán cái túi 0-1 kinh điển 2: dp[j] biểu thị giá trị lớn nhất khi sức chứa là j, công thức chuyển trạng thái dp[j]=max(dp[j],dp[j-w]+v)