URI Online Judge | 1366

Sticks Game

By Ricardo Anido Brazil

Timelimit: 1

There are a lot of fun games that use small colored sticks. The variable used in this problem involves building rectangles. The game consists in, given a set of sticks of variables sizes, draw rectangles on the floor, utilizing the sticks as the sides of the rectangle, with the condition that each stick can be used in only one rectangle, and each side of the rectangle has only one stick. In this game, two kids receive two equal sets of sticks. Wins the game the one who draw the greatest number of rectangles with the sticks.

Given a set of sticks of integer sizes, you must write a software to determinate the greatest number of rectangles that it's possible to draw.


The input contains several test cases. The first line of a test case contains an integer N that indicates the number of different stick sizes (1 ≤ N ≤ 1.000) in the set. Each one of the N following lines contains two integers Ci and Vi, representing respectively a size (1 ≤ Ci ≤ 1.000) and the number of sticks with that size (1 ≤ Vi ≤ 1.000). Each stick size appears at most once in a test case (which means, the values of C1 are different). The end of the input is indicated by N = 0.


For each test case your software must print only one output line, with an integer indicating the maximum number of rectangles that can be formed with the given set of sticks.

Sample Input Sample Output

10 7
50 2
40 2
30 4
60 4
15 3
6 3
12 3
70 5
71 1