Load balancing. (Bronze)
Las vacas del Granjero Juan están paradas en distintas posiciones
en su granja bi-dimensional y los
's y
's son enteros positivos impares de tamaño a lo más
. GJ quiere partir su campo construyendo una cerca larga (efectivamente de longitud infinita) norte-sur con la ecuación
(a será un entero par, por lo tanto asegurándose que no construye la cerca a través la posición de ninguna vaca). El también quiere construir una cerca larga (efectivamente de longitud infinita) este-oeste con la ecuacion
, donde
es un entero par. Esas dos cercan se cruzarán en el punto
y juntas partiran el campo en cuatro regiones.
GJ quiere elegir de manera tal que las vacas que queden en las cuatro regiones resultantes estan razonablemente "balanceadas", sin ninguna region que contenga demasiadas vacas. Sea
el número máximo de vacas que aparezca en una de las cuatro regiones, GJ quiere hacer que
sea tan pequeño como sea posible. Por favor, ayúdelo a determinar este menor valor posible para
.
Para los primeros cinco casos de prueba, se garantiza que será a lo más 100. En todos los casos, se garantiza que
será a lo más 1,000,000.
Entrada
La primera línea de la entrada contiene dos enteros
y
. Las siguientes
líneas contienen la posición de una sola vacas, especificando las coordenadas
.
Salida
Usted debe dar como salida el valor mas pequeño posible de que GJ pude obtener posicionando optimamente sus cercas.
Ejemplo de Entrada
7 10
7 3
5 5
9 7
3 1
7 7
5 3
9 1
Ejemplo de Salida
2
Comments