Module: Recherche binaire par réponse

Problem

Lorsque Petya était à l'école, il participait souvent à des olympiades en informatique, en mathématiques et en physique. Comme il était un garçon assez capable et qu'il étudiait dur, il a reçu des diplômes à plusieurs de ces Olympiades. À la fin de l'école, il avait accumulé n diplômes et, en fin de compte, ils avaient tous la même taille : w — large et h — En hauteur. Petya étudie maintenant dans l'une des meilleures universités russes et vit dans une auberge avec ses camarades de classe. Il a décidé de décorer sa chambre en accrochant ses diplômes pour les olympiades scolaires sur l'un des murs. Comme il est assez difficile de fixer des diplômes sur un mur en béton, il a décidé d'acheter un panneau de liège spécial pour le fixer au mur, et à celui-ci — diplômes. Afin de rendre ce design plus beau, Petya souhaite que le tableau soit carré et prenne le moins de place possible sur le mur. Chaque diplôme doit être placé strictement dans un rectangle mesurant w par h. Les diplômes ne doivent pas être tournés de 90 degrés. Les rectangles correspondant à des diplômes différents ne doivent pas avoir de points intérieurs communs. Il est nécessaire d'écrire un programme qui calculera la taille minimale du côté du plateau dont Petya a besoin pour placer tous ses diplômes.

 

Sortie : Vous devez afficher la réponse au problème.

 

Exemples

#	Entrée	Sortie
1	2 3 10	9
2	1 1 1	1