On their way to the next World Finals, Mr. Ed and his pals are visiting the beautiful city of Moscow. One of their favorite tourism activities is buying souvenirs to bring back home, so they are looking for matryoshkas in a big artisan market close to the Red Square. In the market, there is a very greedy and clever artisan that sells custom sets of matryoshkas. This artisan has n different matryoshkas in stock, each one having a unique identifier i (1 ≤ i ≤ n), a size si and a base price pi. As the artisan is really clever, he offers a special deal to his clients: Assume someone wants to buy the custom set T = {i1, i2, . . . , in} of m matryoshkas. Let us call imax to the identifier of the matryoshka with the maximum size and, in case there are multiple matryoshkas with maximum size, the maximum price in T, then the price one has topaytobuyT is ∑m sij j=1 simax Mr. Ed wants to exploit the artisan’s deal buying exactly k matryoshkas, regardless which are the sizes of each matryoshka. Please determine the minimum number of money he needs to expend. Input The input will contain several test cases. The first line of each test case contains 2 space-separated integers n and k, representing the number of matryoshkas the artisan has in stock and the number of matryoshkasMr. Edwantstobuy(1≤n≤100,000and1≤k≤n). There will follow n lines. The i-th line contains 2 integers si and pi, representing the size and the base price of the i-th matryoshka (1 ≤ si, pi ≤ 106). There may be matryoshkas with the same si and pi. The last test case is followed by a single line containing 2 zeroes. Output For each case, print a single line with a real number with 6 digits after the decimal point representing the minimum price Mr. Ed has to pay to buy k matryoshkas (see format below). Sample Input 32 10 5 44 63 00 Sample Output Case #1: 5.000000 price(T ) = × pimax