Problem
Les vaches du fermier John sont à différents points (x1,y1)…(xn,yn ) ses champs (1≤N≤100 000, tous les xi et yi sont des entiers positifs impairs ne dépassant pas 1 000 000. Le FD veut diviser son champ par une clôture d'infini longueur du nord au sud, décrite par l'équation x=a (a est un nombre entier pair, il est donc assuré que la clôture ne passe par la position d'aucune vache.) Il souhaite également construire une clôture de longueur infinie d'est en ouest, qui est décrit par l'équation y=b, où b est un entier pair Ces deux clôtures se croisent en (a,b) et divisent ensemble le champ en quatre régions.
Le DF veut choisir a et b de telle sorte qu'ils obtiennent un "équilibré" nombre de vaches dans toutes les régions, c'est-à-dire de sorte qu'il n'y a pas de région qui contient trop de vaches. Soit M le nombre maximum de vaches dans ces quatre régions, la FD souhaite que M soit le plus petit possible. Aidez FD à déterminer cette valeur minimale possible pour M.
FORMAT D'ENTREE :
La première ligne d'entrée contient un entier, N. Chacune des n lignes suivantes contient l'emplacement d'une vache, indiqué par ses coordonnées x et y.
FORMAT DE SORTIE :
Imprimer la valeur minimale possible de M pouvant atteindre le PD avec la disposition optimale des clôtures.
Entrez
Sortie
7
73
5 5
7 13
3 1
117
5 3
9 1
2