Nông dân John muốn tặng quà cho \(N\) (\(1 \le N \le 1000\)) chú bò của mình với tổng ngân sách \(B\) (\(1 \le B \le 1\,000\,000\,000\)) đơn vị tiền.

Chú bò \(i\) yêu cầu một món quà có giá \(P(i)\) đơn vị và phí vận chuyển \(S(i)\) đơn vị (do đó tổng chi phí để FJ đặt món quà này là \(P(i)+S(i)\)). FJ có một phiếu giảm giá đặc biệt mà ông có thể dùng để đặt một món quà tùy chọn với giá chỉ bằng một nửa giá thông thường. Vì vậy, nếu FJ dùng phiếu giảm giá cho chú bò \(i\), ông chỉ cần trả \(P(i)/2+S(i)\) cho món quà của chú bò đó. Thuận tiện thay, tất cả các giá trị \(P(i)\) đều là số chẵn.

Hãy giúp FJ xác định số lượng bò lớn nhất mà ông có đủ khả năng tặng quà.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên \(N\) và \(B\) cách nhau bởi dấu cách.
• \(N\) dòng tiếp theo; dòng thứ \(i\) chứa hai số nguyên \(P(i)\) và \(S(i)\) cách nhau bởi dấu cách (\(0 \le P(i),S(i) \le 1\,000\,000\,000\), với \(P(i)\) chẵn).

Dữ liệu ra

• Dòng đầu tiên chứa số lượng bò lớn nhất mà FJ có thể mua quà cho.

Ví dụ

5 24
4 2
2 0
8 1
6 3
12 5

4

Nguồn

USACO 2012 January Contest, Bronze Division — Gifts

Tác giả đề: Kalki Seksaria và Brian Dean, 2012.