Bạn có ~1~ nhân vật cần được tăng chỉ số sức mạnh. Nhân vật của bạn có ~N~ kĩ năng được đánh thứ tự từ ~1~ đến ~N~. Kĩ năng thứ i ~(1 \le i \le N)~ có ~2~ loại chỉ số tăng tiến là ~s_i~ và ~e_i~. Trong lần đầu tiên tăng cấp kĩ năng thứ ~i~, nhân vật của bạn được ~(s_i + e_i)~ chỉ số sức mạnh. Trong các lần tiếp theo tăng cấp kĩ năng thứ ~i~, nhân vật của bạn chỉ nhận được thêm ~e_i~ chỉ số sức mạnh. Bạn có thể tăng cấp ~1~ kĩ năng bất kì không giới hạn số lần. Trò chơi diễn ra trong ~M~ phút, mỗi nhân vật của bạn nhận được ~1~ lần tăng cấp kĩ năng.

Yêu cầu: Hãy tìm chỉ số sức mạnh lớn nhất mà nhân vật của bạn có thể đạt được sau ~M~ phút chơi.

Input

• Dòng đầu tiên chứa 2 số nguyên dương ~N~ và ~M~ ~(1 \le N \le 10^5; 1 \le M \le 10^9)~
• Dòng thứ ~i~ trong ~N~ dòng tiếp theo chứa ~2~ số nguyên dương ~s_i~ và ~e_i~ ~(s_i \le 10^9; e_i \le 10^9)~

Output

• Một số nguyên duy nhất là chỉ số sức mạnh lớn nhất mà nhân vật của bạn có thể đạt được.

Scoring

• Subtask ~1~ (~40~%): ~M = 2~
• Subtask ~2~ (~40~%): ~M \le 100~
• Subtask ~3~ (~20~%): Không có ràng buộc gì thêm.

Ví dụ

Sample Input

3 4
2 2
2 5
5 1

Sample Output

23

Giải thích ví dụ:

Cách nâng cấp tối ưu nhất là:

• Nâng cấp ~3~ lần kĩ năng ~2~.
• Nâng cấp ~1~ lần kĩ năng ~3~.

Tổng chỉ số sức mạnh nhận được sẽ là ~(2 + 5) + 5 + 5 + (5 + 1) = 23~