Cho n đồ vật và 1 cái túi có sức chứa m, mỗi đồ vật có khối lượng và giá trị. Chọn các đồ vật vào túi sao cho tổng khối lượng <=m và tổng giá trị lớn nhất.

Input:
Dòng đầu gồm 2 số nguyên n,m (n<=1000,m<=10^9).

n dòng sau, dòng thứ i gồm 2 số nguyên dương a,b là khối lượng và giá trị của đồ vật thứ i (a<=10^6,b<=10).

Output:

Tổng giá trị lớn nhất.