Matcom Online Grader

En una ciudad de terribles piratas, sucede que cada uno de ellos tiene su casa frente al mar, donde también está anclado su respectivo barco. Un pirata es feliz si desde su casa es visible su barco. La casa de un pirata se considera un punto $x_i$ en la línea de la costa y la ubicación de un barco se representa por un intervalo $[a_i , b_i]$. Un pirata divisa su barco si se cumple que $a_i \leq x_i \leq b_i$. Se sabe además que dos barcos no se intersectan, excepto a lo sumo en sus extremos y que la costa es tan grande, que puede asumirse infinita.El objetivo de este problema es dado las posiciones $x_i$ de las casas de los piratas, ubicar los barcos de forma tal que sea máxima la cantidad de piratas felices. Hay sin embargo una condición que debe ser cumplida y es que el centro del barco del jefe de los piratas, ha de encontrarse frente a su casa.

La primera línea de la entrada es un entero $T$, la cantidad de casos. Cada caso empieza con una línea con el entero $N$ ($1 \leq N \leq 10000$) la cantidad de piratas. Le siguen N líneas, cada una con dos enteros $x_i$ ($-10^9 \leq x_i \leq 10^9$) y $l_i$ ($1 \leq l_i \leq 10^9$) el punto en que se encuentra la casa y la longitud del barco del pirata $i$ respectivamente. El primer pirata es siempre el jefe.