Farmer John cần bò mới! Có $N$ con bán, $1 \le N \le 50,000$, và FJ không được vượt ngân sách $M$, $1 \le M \le 10^{14}$. Bò $i$ giá $P_{i}$, $1 \le P_{i} \le 10^9$. Ông có $K$ phiếu, $1 \le K \le N$, dùng một phiếu cho $i$ thì giá là $C_{i}$, $1 \le C_{i} \le P_{i}$. Mỗi con chỉ một phiếu.

FJ mua tối đa bao nhiêu bò?

Dữ liệu vào

• Dòng $1$: số nguyên $N$, $K$, $M$ cách nhau bằng dấu cách.

• Dòng $2..N+1$: dòng $i+1$ có số nguyên $P_{i}$, $C_{i}$.

Dữ liệu ra

• Dòng $1$: một số nguyên, số bò tối đa mua được.

Ví dụ

Dữ liệu vào 1

4 1 7
3 2
2 2
8 1
4 3

Dữ liệu ra 1

3

Ghi chú

FJ có $4$ bò, $1$ phiếu và ngân sách $7$.

Dùng phiếu cho $3$, mua $1$, $2$, $3$ với phí $3 + 2 + 1 = 6$.

Tác giả bài toán: Neal Wu và Mark Gordon, 2012