Giới thiệu: Đây là đề thi ICPC

Salmon has a business received a big order for M products, they must deliver as soon as possible but there is nothing left in the warehouse, they have to produce from scratch. They have N workers, worker i produce Ai products every day but take 1 day of leave after every Bi days of work. Calculate what is the earliest day they can finish producing M products to deliver

Input

The first line of input contains 2 integers N and M (1 ≤ N ≤ 100, 1 ≤ M ≤ ~10^{15}~), the number of workers and number of products ordered. The next N lines, each has 2 numbers Ai and Bi (1 ≤ Ai , Bi ≤ ~10^{15}~.

Output

Output one integer, the number of days it take.

Examples

Input

2 30
2 5
1 9

Output

11