collectmushrooms5

Problem Description

Gug is collecting mushrooms again. There are N farms from which Gug can collect mushrooms. Each farm only has two mushrooms for Gug to collect. To collect the first mushroom from farm i costs A_i dollars, and collecting the second mushroom from farm i costs B_i dollars. The first mushroom must be collected before the second mushroom. Gug needs M mushrooms in total. Find out the minimum amount of money, in dollars, he must pay.

Input

The first line of input will consist of two integers, N and M.

The next N lines of input will contain two integers each, A_i and B_i.

Output

The output should contain one integer, the minimum amount of money Gug needs to pay.

Limits

For all subtasks: 1 ≤ M ≤ 2N, 1 ≤ A_i, B_i ≤ 10⁹.

Subtask 1 (25%): 1 ≤ N ≤ 1000.

Subtask 2 (10%): 1 ≤ N ≤ 200000, A_i = 1.

Subtask 3 (11%): 1 ≤ N ≤ 200000, A_i = B_i.

Subtask 4 (22%): 1 ≤ N ≤ 200000, A_i ≤ B_i.

Subtask 5 (32%): 1 ≤ N ≤ 200000.

Subtask 6 (0%): Sample Testcases.

Sample Input 1

2 3
1 1
1 1

Sample Output 1

3

Sample Input 2

5 3
10 10
5 5
10 10
6 3
25 5

Sample Output 2

14