Description:

As more and more computers are equipped with dual core CPU, SetagLilb, the Chief Technology Officer of TinySoft Corporation, decided to update their famous product - SWODNIW.

The routine consists of *N* modules, and each of them should run in a certain core. The costs for all the routines to execute on two cores has been estimated. Let's define them as *A _{i}* and

Input:

There are two integers in the first line of input data, *N* and *M* (1 ≤ *N* ≤ 20000, 1 ≤ *M* ≤ 200000) .

The next *N* lines, each contains two integer, *A _{i}* and

In the following

Output:

Output only one integer, the minimum total cost.

Sample Input:

3 1 1 10 2 10 10 3 2 3 1000

Sample Output:

13

Submit