Load Balancing Silver.
¿Cada una de las vacas del Granjero Juan están paradas en posiciones distintas en su granja bidimensional y los 's y los 's son enteros positivos impares de tamaño a lo más 1,000,000). GJ quiere partir su campo construyendo una cerca larga (efectivamente de largo infinito) norte-sur con la ecuación ( será un entero par, asegurando por lo tanto que no construye la cerca a través de la posición de ninguna vaca). El también quiere construir una cerca larga (efectivamente de largo infinito) este-oeste con la ecuación , donde es un entero par. Esas dos cercas se cruzan en el punto y juntas parten su campo en cuatro regiones.
GJ quiere elegir y de tal manera que las vacas que aparecen en las cuatro regiones resultantes están razonablemente "balanceadas", sin ninguna región conteniendo demasiadas vacas. Si es el número máximo de vacas que aparecen en una de las cuatro regiones, GJ quiere hacer tan pequeño como sea posible. Por favor, ayúdelo a determinar este menor valor posible para .
Entrada
La primera línea de la entrada contiene un solo entero, . Cada una de las siguientes líneas contiene la posición de una sola vaca, especificando sus coordenadas y .
Salida
Usted debe dar como salida el menor valor posible de que GJ puede obtener posicionado sus cercas óptimamente.
Ejemplo de Entrada
7
7 3
5 5
7 13
3 1
11 7
5 3
9 1
Ejemplo de Salida
2
Comments