Farmer John cần những con bò mới! Có \(N\) con bò đang được rao bán (\(1 \leq N \leq 50\,000\)), và FJ không được chi quá ngân sách \(M\) đơn vị tiền (\(1 \leq M \leq 10^{14}\)). Bò \(i\) có giá \(P_i\) (\(1 \leq P_i \leq 10^9\)), nhưng FJ có \(K\) phiếu giảm giá (\(1 \leq K \leq N\)); khi dùng một phiếu cho bò \(i\), thay vào đó ông chỉ phải trả \(C_i\) (\(1 \leq C_i \leq P_i\)). Dĩ nhiên, FJ chỉ có thể dùng một phiếu giảm giá cho mỗi con bò.

Số bò lớn nhất mà FJ có đủ khả năng mua là bao nhiêu?

Dữ liệu vào

• Dòng đầu tiên chứa ba số nguyên cách nhau bởi dấu cách: \(N\), \(K\) và \(M\).
• \(N\) dòng tiếp theo: dòng thứ \(i+1\) chứa hai số nguyên \(P_i\) và \(C_i\).

Dữ liệu ra

In ra một số nguyên duy nhất là số bò lớn nhất mà FJ có đủ khả năng mua.

Ví dụ

4 1 7
3 2
2 2
8 1
4 3

3

Nguồn

USACO 2012 February Contest, Gold Division — Cow Coupons. Tác giả đề: Neal Wu và Mark Gordon (2012).

https://usaco.org/index.php?page=viewproblem2&cpid=118