## 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^{9}.

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