Phiếu Giảm Giá Bò

Đ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

Farmer John có $N$ con bò và $K$ phiếu giảm giá. Mỗi con bò $i$ có giá thông thường $P_{i}$ và giá khi dùng phiếu $C_{i}$ (với $C_{i} \leq P_{i}$ ). Farmer John có ngân sách $M$ đồng và muốn mua được nhiều bò nhất có thể.

Mỗi phiếu giảm giá chỉ dùng được cho một con bò, và mỗi con bò chỉ dùng được tối đa một phiếu. Tổng chi phí không được vượt quá $M$ .

Dữ liệu vào

Dòng 1: Ba số nguyên $N$ , $K$ , $M$
$N$ dòng tiếp theo: Hai số nguyên $P_{i}$ , $C_{i}$ — giá thông thường và giá khi dùng phiếu của bò thứ $i$

Dữ liệu ra

In ra số bò tối đa mà Farmer John có thể mua.

Ràng buộc

$1 \leq K \leq N \leq 50 000$
$1 \leq M \leq 10^{14}$
$1 \leq C_{i} \leq P_{i} \leq 10^{9}$

Ví dụ

Input	Output	Giải thích
4 1 7 3 2 2 2 8 1 4 3	3	Dùng phiếu cho bò thứ 3 (giá 1), mua bò 1 (giá 3) và bò 2 (giá 2). Tổng = 1+3+2 = 6 ≤ 7.
3 1 58 26 23 28 24 27 25	2	Dùng phiếu cho bò thứ 1 (giá 23), mua bò 3 (giá 27). Tổng = 23+27 = 50 ≤ 58.

Bình luận

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