The concept of cloud computing has become fairly popular lately. One of the main kinds of cloud computing is known as IaaS (Infrastructure as a Service), in which servers can be rented and managed via the Internet.

Cloud, Inc. is an IaaS provider. The company is designing a new data center for its clients. Through some research, they found out that their clients, as a whole, need K servers, each of which needs to be able to withstand a certain level of demand. If we assume that the cost of a server always grows with the demand which that server can process, the best solution in terms of cost is to buy K servers explicitly designed to meet the exact requirements of the corresponding client.

However, having K different hardware configurations in the data center is extremely problematic for the system administrators. To simplify, they demand that no more than L distinct server types be bought. A server that meets a demand c also meets any demand smaller than c.

A possible solution is to buy only one server type that is able to meet the highest client demand, as it will also be able to meet all other demands. On the other hand, the cost of such a solution can be prohibitively high. Considering that you can buy up to L different kinds of servers, there's likely a better option. For instance, suppose that there are 3 clients, with demands 3, 7 and 16. Assume that the cost of a server meeting demands up to 3 is of R$ 1500 (1500 Brazilian reais), the cost of a server that meets demand 7 is R$ 5500 and the cost of a server that meets demand 16 is R$ 19200. If you want to buy at most 2 kinds of servers to satisfy all clients, you have four possibilities:

• Buying three servers with capacity 16, at a total cost of R$ 57600;
• Buying two servers with capacity 16 and one with capacity 7, at a total cost of R$ 43900;
• Buying two servers with capacity 16 and one with capacity 3, at a total cost of R$ 39900;
• Buying one server with capacity 16 and two servers with capacity 7, at a total cost of R$ 30200.

Among these options, the one with the least total cost is the last one.

You will receive a list of K requested demands and the price of a server type that meets the corresponding demand. Determine the lowest total cost to buy K servers in a way such that all requested demands are met and at most L different types of servers are bought.

Notes

• Each server is used by one and only one client. A server with capacity 4 may not be used by two clients with demand 2 each.
• Let D_i and D_j be two demands, and P_i, P_j prices associated to the servers that meet those demands. If D_i < D_j, then P_i ≤ P_j.

Input

There are several test cases.

Each test case begins with a line containing integers K and L, respectively the number of servers to be bought and the maximum allowed number of distinct server types (1 ≤ L ≤ K ≤ 2000). K lines follow, each of which containing two integers D and P, respectively the demand of a client and the smallest price of a server which meets that demand (1 ≤ D ≤ 2000, 1 ≤ P ≤ 100000). If the same value of D is present on more than one line, then both lines will have the same value for P.

The input ends when K = L = 0, and this case should not be processed.

Output

For each test case, print a line with an integer T, which is the lowest total cost obtainable.

Example

Input:
10 3
1 1
2 4
3 5
4 7
5 8
6 12
7 13
8 18
9 19
10 21
0 0

Output:
129

The best option to buy servers of 3 kinds that meet the required demands is to buy:

• 3 servers of capacity 10, which account for client demands 10, 9 and 8;
• 2 servers of capacity 7, which account for client demands 7 and 6;
• 5 servers of capacity 5, which account for all other demands.

Total cost is 3*21 + 2*13 + 5*8 = 129.