B"There are n glasses on the table numbered 1, ldots, n . The glass i can hold up to a_i units of water, and currently contains b_i units of water. You would like to choose k glasses and collect as much water in them as possible. To that effect you can pour water from one glass to another as many times as you like. However, because of the glasses' awkward shape (and totally unrelated to your natural clumsiness), each time you try to transfer any amount of water, half of the amount is spilled on the floor. Formally, suppose a glass i currently contains c_i units of water, and a glass j contains c_j units of water. Suppose you try to transfer x units from glass i to glass j (naturally, x can not exceed c_i ). Then, x / 2 units is spilled on the floor. After the transfer is done, the glass i will contain c_i - x units, and the glass j will contain min(a_j, c_j + x / 2) units (excess water that doesn't fit in the glass is also spilled). Each time you transfer water, you can arbitrarlly choose from which glass i to which glass j to pour, and also the amount x transferred can be any positive real number. For each k = 1, ldots, n , determine the largest possible total amount of water that can be collected in arbitrarily chosen k glasses after transferring water between glasses zero or more times. The first line contains a single integer n ( 1 <= q n <= q 100 ) -- the number of glasses. The following n lines describe the glasses. The i -th of these lines contains two integers a_i and b_i ( 0 <= q b_i <= q a_i <= q 100 , a_i > 0 ) -- capacity, and water amount currently contained for the glass i , respectively. Print n real numbers -- the largest amount of water that can be collected in 1, ldots, n glasses respectively. Your answer will be accepted if eac"...