Problem Description

There is a long flower bed in your garden that extends infinitely to the east. You have decided to plant $N$ types of flowers in this flower bed, which is currently empty. For convenience, these types of flowers are referred to as Flower $1, 2, \ldots, N$. Also, the position $p$ centimeters from the west end of the flower bed is called position $p$.

Flower $i$ ($1 \leq i \leq N$) will be planted at position $w_i$ and then planted infinitely to the east at intervals of $d_i$ centimeters. That is, Flower $i$ will be planted at positions $w_i, w_i + d_i, w_i + 2d_i, \ldots$. Multiple flowers can be planted at the same position.

Determine the position of the $K$-th flower planted from the west. Note that if multiple flowers are planted at the same position, they are counted individually.

Input Format

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

$N$ $K$ $w_1$ $d_1$ $:$ $w_N$ $d_N$

Output Format

When the $K$-th flower planted from the west is at position $X$, output the value of $X$. (The flower planted furthest to the west is counted as the 1st.)

Sample Input and Output

Sample Input #1

2 6
20 10
25 15

Sample Output #1

50

Sample Input #2

3 9
10 10
10 10
10 10

Sample Output #2

30

Sample Input #3

1 1000000000
1000000000000000000 1000000000

Sample Output #3

1999999999000000000

Notes/Hints

Constraints

• $1 \leq N \leq 10^5$
• $1 \leq K \leq 10^9$
• $1 \leq w_i \leq 10^{18}$
• $1 \leq d_i \leq 10^9$
• All input values are integers.

Sample Explanation 1

Two types of flowers are planted at the following positions:
- Flower 1: positions $20, 30, 40, 50, 60, \ldots$
- Flower 2: positions $25, 40, 55, 70, 85, \ldots$
The 6th flower from the west is Flower 1 planted at position $50$. Note that the two flowers planted at position $40$ are counted individually.

Sample Explanation 2

Three flowers are planted at each of the positions $10, 20, 30, \ldots$. Therefore, the 9th flower from the west is planted at position $30$.

见题面 Input 部分

见题面 Output 部分