Game of Rods
By 
Brazil
By Brazil
There are many fun games that use small colored sticks. The variant used in this problem involves the construction of rectangles. The game consists of, given a set of rods of varied lengths, to draw rectangles on the ground, using the rods as sides of the rectangles, each rod being used in only one rectangle, and each rectangle side is formed by a single rod. In this game, two children receive two equal sets of rods. The child who draws the largest number of rectangles with the set of rods win the game. Given a set of sticks of integer lengths, you must write a program to determine the largest number of rectangles that can be drawn.
The input contains several test cases. The first line of a a test case contains a integer N which indicates the number of different lengths of rods (1 ≤ N ≤ 1.000) in the set. Each one of N following lines contains two integers Ci and Vi, representing respectively a length (1 ≤ Ci ≤ 10.000) and the number of rods with this lenght (1 ≤ Vi ≤ 1.000). Each rod length appears at most once in a test set (that is, the values Ci are distincts). The end of input is indicated by N = 0.
To each test case of input your program should to produce a single line at the output, containing an integer, indicating the maximum number of rectangles that can be formed with the set of rods given.
| Input Sample | Output Sample |
|
1 10 7 4 50 2 40 2 30 4 60 4 5 15 3 6 3 12 3 70 5 71 1 0 |
1 3 2 |