Фермер Джон решил потренировать своих коров в акробатике. Сначала он
взвесил своих коров и определил, что они имеют \(N\) (\(1\le N\le 2\cdot 10^5\))
различных весов. В частности, для каждой \(i\in [1,N]\), \(a_i\) из его
коров имеют вес \(w_i\) (\(1\le a_i\le 10^9, 1\le w_i\le 10^9\)).
Его наиболее популярный трюк включает коров, формирующих сбалансированную башню.
Башня это последовательность коров, стоящих одна на другой.
Башня называется сбалансированной, если каждая корова с коровой над ней
имеет вес не менее чем на (\(1\le K\le 10^9\)) больший, чем вес коровы непосредственно
над ней. Каждая корова может быть частью не более чем одной сбалансированной башни.
Если ФД хочет создать не более \(M\) (\(1 \le M \le 10^9\)) сбалансированных башен
из своих коров, какое наибольшее количество коров может быть частью некоторой башни?
ФОРМАТ ВВОДА (с клавиатуры):
Первая строка содержит три разделённых пробелом целых числа
\(N\),
\(M\),
\(K\).
Следующие \(N\) строк содержат два разделённых пробелом целых числа \(w_{i}\) и \(a_i\).
Гарантируется, что все \(w_i\) различны.
ФОРМАТ ВЫВОД (на экран):
Выведите максимальное количество коров в сбалансированных башнях, если ФД
поможет сформировать эти башни оптимально.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 5 2
9 4
7 6
5 5
|
14
|