Después de varias equivocaciones ¡el Inspector Craig ha logrado encontrar a los fugitivos de la Isla de los Truhanes y Caballeros! Para disculparse con los habitantes por estos momentos de tensión, el alcalde ha decidido hacer felices a sus habitantes, ¿y qué mejor manera que limpiando las calles de la Isla? Por supuesto, no siempre es posible tener a todos felices, pero aún así él quiere hacer feliz a la mayor cantidad posible de habitantes.

La Isla consta de ~n~ calles una después de la otra y todas ellas están llenas de basura. Hay ~m~ habitantes en la Isla cada uno de los cuales desea que sean limpiadas las calles del intervalo ~[l_i \dots r_i]~. ¿Cuántos deseos de los habitantes puede cumplir el alcalde cuando solo tiene dinero para limpiar ~k~ calles de la Isla?

Subtareas

Para todas las subtareas: ~1 \le k \le n~, ~1 \le l \le r \le n~

• Subtarea 1 (27 puntos): ~1 \le n \le 15~, ~0 \le m \le 15~.
• Subtarea 2 (41 puntos): ~1 \le n \le 100~, ~1 \le m \le 100~.
• Subtarea 3 (32 puntos): ~1 \le n \le 500~, ~1 \le m \le 1000~.

Entrada

La primera línea tiene tres números enteros ~n~, ~m~ y ~k~. Las calles de la Isla están numeradas ~1,2,\dots,n~.

Las siguientes ~m~ líneas describen los deseos de los habitantes. Cada línea tiene dos números enteros ~l~ y ~r~: el habitante quiere que se limpien las secciones de la carretera ~[l \dots r]~.

Salida

Imprime un número entero: el número máximo de deseos que puede cumplir el alcalde.

Ejemplos

Entrada 1

6 4 4
1 3
3 4
2 3
3 6

Salida 1

3

Puede limpiar las calles ~[1 \dots 4]~ y cumplir los primeros tres deseos.

Entrada 2

3 3 2
1 1
1 3
3 3

Salida 2

2

Puede limpiar las calles ~1~ y ~3~ y cumplir el primer y tercer deseo.