Trang trại gà của nhà Bé Bo có ~ n ~ con gà siêu trứng đánh số từ ~ 1 ~ đến ~ n ~. Con gà ~ i~ ~(1≤i≤n) ~ đẻ quả trứng đầu tiên ở giây ~ p_i ~, sau đó cứ ~ t_i ~ giây tiếp theo sẽ đẻ thêm một quả trứng.

Yêu cầu: Bạn hãy viết chương trình tính thời gian nhỏ nhất (tính bằng giây) để Bé Bo thu được ít nhất ~ x ~ quả trứng.

Dữ liệu vào:

• Dòng thứ nhất chứa hai số nguyên dương ~ n,x; ~
• ~ n ~dòng tiếp theo, dòng thứ ~ i~ ~(1≤i≤n) ~ chứa hai số nguyên dương ~ p_i,t_i 1≤p_i,t_i≤500. ~

Kết quả:

• Một số nguyên duy nhất là thời gian nhỏ nhất để Bé Bo thu được ít nhất ~ x ~ quả trứng.

Ví dụ:

Input 1:

2 3
10 30
5 25 

Output 1:

30 

Giải thích ví dụ 1

• Con gà số 1 đẻ quả trứng đầu tiên ở giây 10, đẻ quả trứng thứ 2 ở giây 40, quả trứng thứ 3 ở giây 70,…
• Con gà số 2 đẻ quả trứng đầu tiên ở giây 5, đẻ quả trứng thứ 2 ở giây 30, quả trứng thứ 3 ở giây 55,…
• Vậy chỉ sau 30 giây thì tổng số trứng thu được là 3 quả.

Input 2:

2 3
10 5
5 10 

Output 2:

15 

Giải thích

• Con gà số 1 đẻ quả trứng đầu tiên ở giây 10, đẻ quả trứng thứ 2 ở giây 15,…
• Con gà số 2 đẻ quả trứng đầu tiên ở giây 5, đẻ quả trứng thứ 2 ở giây 15,…

Vậy:

• Tổng số trứng thu được sau 5 giây: 1
• Tổng số trứng thu được sau 10 giây: 2
• Tổng số trứng thu được sau 15 giây: 4

Ràng buộc:

• 20% số test tương ứng với 20% số điểm có ~ n=1, x≤10^{15} ~;
• 45% số test tương ứng với 45% số điểm có ~ n≤20, x≤1000 ~;
• 35% số test tương ứng với 35% số điểm có ~ n≤20, x≤10^{15} ~.