Mua Quà

Có $N$ món quà, món thứ $i$ có giá $P_i$ và phí giao hàng $S_i$. Bạn có ngân sách $B$ và một phiếu giảm giá giúp giảm giá một món xuống còn $P_i/2$ (phí giao không đổi). Tất cả $P_i$ đều chẵn.

Hãy tìm số món quà tối đa có thể mua.

Dữ liệu vào

• Dòng 1: Hai số nguyên $N$ và $B$
• $N$ dòng tiếp theo: Hai số nguyên $P_i$ và $S_i$

Dữ liệu ra

• In ra số món quà tối đa.

Ràng buộc

• $1\le N\le 1000$
• $1\le B\le {10}^9$
• $0\le P_i,S_i\le {10}^9$

Ví dụ