#### Registered Users Only

Please login to utilize this feature.

Do note that this website only supports submissions in C++.

## 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*dollars. The first mushroom must be collected before the second mushroom. Gug needs

_{i}*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

### Tags

### Subtasks and Limits

Subtask | Score | #TC | Time | Memory | Scoring |
---|---|---|---|---|---|

1 | 25 | 22 | 1s | 256MB | Minimum |

2 | 10 | 21 | 1s | 256MB | Minimum |

3 | 11 | 21 | 1s | 256MB | Minimum |

4 | 22 | 61 | 1s | 256MB | Minimum |

5 | 32 | 102 | 1s | 256MB | Minimum |

6 | 0 | 2 | 1s | 256MB | Minimum |

### Judge Compile Command

g++-7 ans.cpp -o collectmushrooms5 -Wall -static -O2 -lm -m64 -s -w -std=gnu++17 -fmax-errors=512