Farmer John đã quyết định cho đàn bò biểu diễn nhào lộn! Trước tiên, FJ cân đàn bò và thấy chúng có \(N\) mức cân nặng đôi một khác nhau (\(1\le N\le 2\cdot 10^5\)). Cụ thể, với mỗi \(i\in[1,N]\), có \(a_i\) con bò nặng \(w_i\) (\(1\le a_i\le 10^9\), \(1\le w_i\le 10^9\)).

Tiết mục nổi tiếng nhất của ông là cho các con bò tạo thành những tháp cân bằng. Một tháp là một dãy bò, trong đó mỗi con được xếp lên trên con tiếp theo. Một tháp được gọi là cân bằng nếu mọi con bò có một con khác nằm ngay phía trên đều nặng hơn con bò ngay phía trên đó ít nhất \(K\) (\(1\le K\le 10^9\)). Mỗi con bò chỉ có thể thuộc tối đa một tháp cân bằng.

Nếu FJ muốn tạo không quá \(M\) (\(1\le M\le 10^9\)) tháp bò cân bằng, nhiều nhất bao nhiêu con bò có thể thuộc một tháp nào đó?

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\), \(M\) và \(K\).

\(N\) dòng tiếp theo, mỗi dòng chứa hai số nguyên cách nhau bởi dấu cách \(w_i\) và \(a_i\). Đảm bảo tất cả \(w_i\) đôi một khác nhau.

Dữ liệu ra

In số bò lớn nhất có thể nằm trong các tháp cân bằng nếu FJ giúp chúng tạo tháp một cách tối ưu.

Ví dụ

3 5 2
9 4
7 6
5 5

14

3 5 3
5 5
7 6
9 4

9

Phân nhóm

• Trong dữ liệu 3–5, \(M\leq 5000\) và tổng số bò không vượt quá \(5000\).
• Trong dữ liệu 6–11, tổng số bò không vượt quá \(2\cdot 10^5\).
• Dữ liệu 12–17 không có ràng buộc bổ sung.

Nguồn

USACO 2023 December Contest, Silver — Bovine Acrobatics: https://usaco.org/index.php?page=viewproblem2&cpid=1350

Tác giả bài toán: Eric Hsu