The village of Tung Tung Tung has a legendary tradition. Every morning, ~n~ percussionists gather to wake the residents with a rhythmic triple-hit pattern. To ensure everyone is awake, the village elder has decreed that the music must continue until the total number of drum beats across the entire village reaches at least ~k~.

Each percussionist ~i~ has a Triple T signature defined by two integers: the period (~p_i~) and the interval (~d_i~).

A single 'Triple T' sequence for percussionist ~i~ consists of exactly ~3~ drum beats played within a period of time. Say the sequence starts at time ~T~, each of the beats will occur as follows:

1. The first beat at ~T~.
2. The second beat at ~T+d_i~.
3. The third beat at ~T+2 d_i~.

The percussionists are very disciplined. The ~j~-th sequence (~j = 1, 2, 3, \dots~) for percussionist ~i~ starts exactly at time ~(j-1) \times p_i~. Therefore, the beats for percussionist ~i~ occur at:

• ~(j-1) \times p_i~
• ~(j-1) \times p_i + d_i~
• ~(j-1) \times p_i + 2 d_i~

All percussionists start their first sequence at ~T = 0~. Your task is to find the minimum time ~T~ required such that the total number of drum beats produced by all ~n~ percussionists up to and including time ~T~ is at least ~k~.

Input

The first line contains two integers ~n~ and ~k~ ~(1 \le n \le 2 \times 10^4~, ~1 \le k \le 10^9)~, the number of percussionists and the total number of beats required.

Each of the next ~n~ lines contains two integers ~p_i~ and ~d_i~ ~(1 \le p_i \le 10^9~, ~1 \le d_i \le 10^9~, ~2d_i < p_i)~.

Output

Print a single integer, the minimum time ~T~ such that the total number of beats that have occurred by that time is at least ~k~.

The answer is guaranteed to be less than or equal to ~10^{18}~.

Example

Input 1

2 10
10 2
15 3

Output 1

15

For Percussionist 1 (~p=10, d=2~):

• Beats occur at ~T = 0, 2, 4~ (1st period)
• Beats occur at ~T = 10, 12, 14~ (2nd period)
• Beats occur at ~T = 20, 22, 24~ (3rd period)

For Percussionist 2 (~p=15, d=3~):

• Beats occur at ~T = 0, 3, 6~ (1st period)
• Beats occur at ~T = 15, 18, 21~ (2nd period)

At ~T = 14~:

• Percussionist 1 has hit 6 times.
• Percussionist 2 has hit 3 times.
• Total beats = 9 (Less than ~k=10~).

At ~T = 15~:

• Percussionist 1 has hit 6 times.
• Percussionist 2 has hit 4 times (the hit at ~T=15~ is the start of their 2nd period).
• Total beats = 10 (Matches ~k=10~).

The minimum time is ~15~.

Input 2

5 3
100 10
100 10
100 10
100 10
100 10

Output 2

0

Input 3

1 2
10 1

Output 3

1