Một cửa hàng đã nhờ các dev của D18PROPTIT giúp họ tối đa doanh thu.

Kho chứa của họ của ~N~ mặt hàng: mỗi mặt hàng có một cân nặng là ~m~ và số lượng mặt hàng đó trong kho là ~k~ (ví dụ mặt hàng A có khối lượng 3kg và số lượng A đang có trong kho là 2 ứng với ~m = 3~ và ~k = 2~).

Khách hàng của họ yêu cầu một chuyến xe với khối lượng ~P~. Nhiệm vụ của bạn viết một chương trình ứng với ~N~ mặt hàng trong kho chọn ra một tập gồm các hàng hóa thỏa mãn 2 giá trị:

1. Tổng khối lượng hàng hóa được chọn là ~P~.
2. Tập chứa các mặt hàng bạn chọn phải đáp ứng số mặt hàng khác nhau là lớn nhất.

Input

• Dòng đầu tiên gồm 2 số nguyên ~N~ và ~P~. Trong đó là ~N~ số mặt hàng đang có trong kho, ~P~ là khối lượng khách hàng yêu cầu.
• ~N~ dòng tiếp theo mỗi dòng gồm 2 số nguyên ~k~ và ~m~ tương ứng ~k~ là số lượng và ~m~ là khối lượng mặt hàng đó.

Giới hạn:

• ~1 \le N \e 20~
• ~ 20 \le P \le 5000~
• ~20 \le m \le 500~
• ~1 \le k \le 20~

Output

• In ra 1 số nguyên duy nhất số mặt hàng khác nhau lớn nhất có thể thỏa mãn yêu cầu bài toán.
• Nếu không có cách chọn nào có tổng bằng ~P~, in ra -1.

Sample

Input #1

4 320
1 20
1 50
1 100
2 150

Output #1

4

Hint

Giải thích test 1. Có tất cả các cách chọn sau:

• Mặt hàng A1 có 2 cách chọn: chọn ra 0 mặt hàng A1 hoặc chọn ra 1 măt hàng A1.
• Mặt hàng A2,A3 tương tự có 2 cách chọn.
• Mặt hàng A4 có 3 cách chọn: chọn ra {0,1,2} mặt hàng A4.

Có tất cả 222*3=24 cách chọn các mặt hàng trong kho. Trong đó:

• Số mặt hàng khác nhau lớn nhất là 4: có 2 cách sau:
  • Cách 1: chọn toàn bộ các mặt hàng trong kho khi đó tổng trọng lượng là 120+150+1100+2150=470>320do đó cách này không thỏa mãn.
  • Cách 2: tất cả các mặt hàng đều được chọn với số lượng = 1. Khi đó tổng trọng lượng là 320 . Cách chọn này thỏa mãn yêu cầu bài toán và số mặt hàng khác nhau = 4.

Các cách chọn khác 2 cách chọn trên thì số mặt hàng khác nhau luôn < 4.Vì vậy đáp án bài toán là 4.

Chú ý:Ta đang tối ưu số mặt hàng khác nhau vì vậy mà cách chọn 2 mặt hàng A4 và 1 mặt hàng A1 có tổng = 320 không thỏa mãn mặc dù tổng khối lượng = 320 nhưng số mặt hàng khác nhau chỉ là 2.

Problem source: CLB Lập Trình PTIT