Esta noche Tres-Veltör no tiene sueño, así que ha decidido jugar a uno de sus juegos favoritos, el OSU! En este juego hay que tocar una canción como si fuera un piano. La canción dura ~N~ milisegundos, durante el milisegundos ~a_i~ Tres-Veltör tiene que tocar la nota ~b_i (1 \leq b_i \leq 4)~, nunca van a existir dos notas iguales al mismo tiempo. El problema es que Tres-Veltör aun es un humano por lo tanto tiene ciertas limitaciones. Cuando él toca la nota ~b_i~ la tiene que tocar con el dedo ~b_i~ y este dedo y sus adyacentes (note que el primero y el último solo tienen un adyacente) no pueden usarse hasta dentro de ~X~ milisegundos, esta cualidad es acumulativa, por lo cual, si por ejemplo el usa el dedo 1 y el dedo 3, el dedo 2 no lo podrá usar hasta dentro de ~2X~ milisegundos. Tampoco puede usar dos dedos adyacentes a la vez. Tres-Veltör quiere que le ayudes a saber cuál es la máxima cantidad de notas que él puede tocar.

Entrada

La primera linea contiene tres enteros ~N~,~K~ y ~X~ (~1 \leq N \leq 10^3~), (~1 \leq K \leq 10^5~) y (~1 \leq X \leq 10~).

Las siguientes ~K~ lineas contienen ~K~ pares de números ~a~ y ~b~ (~1 \leq a \leq N~), (~1 \leq b \leq 4~) que significan que en el millisegundo ~a~ se va a tocar la nota ~b~.

Salida

Un único número, la mayor cantidad de notas que puede tocar Tres-Veltör.

Puntuación

La evaluación del ejercicio no tendrá puntuación parcial.

Ejemplo de Entrada

20 5 3
1 1
1 2
4 3
4 4
7 2

Ejemplo de Salida

3