Problem Description

There are $ N $ machines in a factory for making presents. The $ i(1≦i≦N) $ machine can initially make one present in $ a_i $ seconds.
However, each time a machine makes a present, only that machine deteriorates, increasing the time it takes to make a present by $ b_i $ seconds.
Therefore, it takes $a_i\ +\ (s_i-1)×b_i$ seconds to make the $ s_i $th present with the $ i(1≦i≦N) $ machine.
Also, due to low power supply in the factory, multiple machines cannot operate simultaneously.

Dolphin wants to manufacture $ K $ presents in the shortest possible time.
Find the minimum total time required to manufacture the presents.

Input Format

The input is given from the standard input in the following format:

$ N $ $ K $ $ a_1 $ $ b_1 $ $ : $ $ a_N $ $ b_N $

Output Format

Output the minimum total time required to manufacture the presents.

Sample Input and Output

Sample Input #1

3 3
1 3
2 0
3 4

Sample Output #1

5

Sample Input #2

10 100000
22 59
26 60
72 72
47 3
97 16
75 41
82 77
17 97
32 32
28 7

Sample Output #2

7521307799

Sample Input #3

1 100000
1000000000 1000000000

Sample Output #3

5000050000000000000

Notes/Hints

Constraints

• $ 1≦N≦10^5 $
• $ 1≦K≦10^5 $
• $ 1≦a_i≦10^9 $
• $ 0≦b_i≦10^9 $
• All inputs are integers.

Sample Explanation 1

When the machines in the factory are operated the following number of times, it is possible to make 3 presents in 5 seconds: - Machine #1: 1 time - Machine #2: 2 times - Machine #3: 0 times

Sample Explanation 2

Be careful of overflow.

见题面 Input 部分

见题面 Output 部分