Phiếu Giảm Giá Bò

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\le 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\le K\le N\le 50000$
• $1\le M\le {10}^{14}$
• $1\le C_i\le P_i\le {10}^9$

Ví dụ