Mua Quà

Điểm: 1,00 (OI)

Giới hạn thời gian: 1.0s

Python 3 5.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Tác giả:

huunguyen

Dạng bài

Ngôn ngữ cho phép

C++, Go, Java, Kotlin, Pascal, Python, Scratch

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 \leq N \leq 1 000$
$1 \leq B \leq 10^{9}$
$0 \leq P_{i}, S_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
5 24 4 2 2 0 8 1 6 3 12 5	4	Dùng phiếu giảm giá cho món 3 (giá 4+1=5), mua thêm món 1,2,4. Tổng = 6+2+5+9 = 22 ≤ 24

Bình luận

Không có bình luận tại thời điểm này.