El Granjero Juan ha decidido que sus vacas hagan acrobacias. Primero, GJ pesa a sus vacas y encuentran que tienen ~N~ pesos distintos. En particular, para cada ~i \in [1,N]~, ~a_i~ de sus vacas tienen un peso de ~w_i~.

Su número más popular involucra que las vacas formen torres balanceadas. Una torre es una sucesión de vacas donde cada vaca está apilada encima de la anterior. Una torre es balanceada si cada vaca con una vaca directamente encima de ella tiene peso al menos ~K~ mayor que el peso de la vaca directamente encima de ella. Cualquier vaca puede ser parte de a lo más una torre balanceada.

Si GJ quiere crear a lo más ~M~ torres balanceadas de vacas, a lo más cuántas vacas pueden ser parte de alguna torre?

Entrada

La primera línea contiene tres enteros separados por espacios, ~N~, ~M~, y ~K~.

Las ~N~ líneas siguientes contienen dos enteros separados por espacio, ~w_i~ y ~a_i~. Se garantiza que todos los ~w_i~ son distintos.

Salida

Dé el número máximo de vacas en torres balanceada si GJ ayuda a las vacas a formar torres óptimamente.

Restricciones

• ~1 \leq N \leq 2 \cdot 10^5~
• ~1 \leq a_i \leq 10^9~
• ~1 \leq w_i \leq 10^9~
• ~1 \leq K \leq 10^9~
• ~1 \leq M \leq 10^9~

Ejemplo #1 de Entrada

3 5 2
9 4
7 6
5 5

Ejemplo #1 de Salida

14

GJ puede crear cuatro torres balanceadas con vacas de pesos 5, 7 y 9, y una torre balanceada con vacas de pesos 5 y 7.

Ejemplo #2 de Entrada

3 5 3
5 5
7 6
9 4

Ejemplo #2 de Salida

9

GJ puede crear cuatro torres balanceadas con vacas de pesos 5 y 9, y una torre balanceada con una vaca de peso 7. Alternativamente, puede crear cuatro torres balanceadas con vacas de pesos 5 y 9, y una torre balanceada con una vaca de peso 5.

USACO 2023 December Contest, Silver Problem 1. Bovine Acrobatics.