Saltos en el plano P35559

Statement

Se os dan $n$ puntos $\{p_1, \dots, p_n\}$ con coordenadas enteras en el plano, con $p_i = (x_i, y_i)$ . Vuestra tarea es calcular el máximo número de saltos que se pueden realizar entre esos puntos, de manera que en ningún salto se decrementen ni la coordenada $x$ ni la $y$ . Es decir, hay que calcular una secuencia de tamaño máximo de puntos diferentes $p_{s_1}, \dots, p_{s_m}$ tal que $s_i \in \{1, \dots, n\}$ , y para todo $1 \le i < m$ , se cumpla $x_{s_i} \le x_{s_{i+1}}$ e $y_{s_i} \le y_{s_{i+1}}$ .

Por ejemplo, si la colección de puntos es $\{(1, 4), (3, 1), (5, 2), (5, 3), (7, 1), (7, 3), (8, 4) \}$ , se pueden conseguir cuatro saltos, como esta figura demuestra:

(100,60)

(00,20)(90,20) (00,30)(90,30) (00,40)(90,40) (00,50)(90,50) (00,60)(90,60) (10,10)(10,60) (20,10)(20,60) (30,10)(30,60) (40,10)(40,60) (50,10)(50,60) (60,10)(60,60) (70,10)(70,60) (80,10)(80,60) (90,10)(90,60)

(00,10)(90,10) (00,10)(00,60)

(10,04)1 (20,04)2 (30,04)3 (40,04)4 (50,04)5 (60,04)6 (70,04)7 (80,04)8

(-5,20)1 (-5,30)2 (-5,40)3 (-5,50)4

(30,20)(50,30) (50,30)(50,40) (50,40)(70,40) (70,40)(80,50)

(10,50)2 (30,20)2 (50,30)2 (50,40)2 (70,20)2 (70,40)2 (80,50)2

Entrada

La entrada consiste en diversos casos, cada uno con $n$ , seguida de $n$ puntos diferentes. Podéis asumir $n \ge 1$ , y que el valor absoluto de cada coordenada es como mucho $10^6$ .

Salida

Para cada caso, escribid el máximo número de saltos posibles.

Puntuación

test-1: Entradas donde $n \le 5$ , todas las $x_i$ son diferentes entre si, y todas las $y_i$ son diferentes entre si, como el Ejemplo 1.

test-2: Entradas donde $n \le 5$ , como el Ejemplo 2.

test-3: Entradas donde $n \le 200$ , todas las $x_i$ son diferentes entre si, y todas las $y_i$ son diferentes entre si.

test-4: Entradas donde $n \le 200$ , como el Ejemplo 3.

test-5: Entradas donde $n \le 10^4$ , todas las $x_i$ son diferentes entre si, y todas las $y_i$ son diferentes entre si.

test-6: Entradas donde $n \le 10^4$ .

Public test cases

Input

1  3 3
2  1 -2  -1 1
2  0 0  -1 -1

Output

0
0
1

Input

3  0 0  -2 -2  -1 -1
3  2 0  1 1  0 2
3  0 0  0 1  0 2
3  0 0  -1 0  -2 0

Output

Input

7  1 4  3 1  5 2  5 3  7 1  7 3  8 4

Output

Information

Author: Salvador Roura
Language: Spanish
Official solutions: C++
User solutions