Trò chơi

Bạn có một nhân vật cần được tăng chỉ số sức mạnh.

Nhân vật có \(N\) kỹ năng, được đánh số từ \(1\) đến \(N\).
Kỹ năng thứ \(i\) có hai chỉ số tăng tiến là \(s_i\) và \(e_i\).

• Lần đầu tiên tăng cấp kỹ năng \(i\), nhân vật nhận được \((s_i + e_i)\) điểm sức mạnh.
• Từ lần tăng cấp thứ hai trở đi của kỹ năng \(i\), mỗi lần chỉ nhận thêm \(e_i\) điểm sức mạnh.

Bạn có thể tăng cấp một 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 phút, nhân vật được thực hiện đúng một lần tăng cấp.

Yêu cầu:
Hãy tính chỉ số sức mạnh lớn nhất mà nhân vật có thể đạt được sau \(M\) phút.

\InputFile
\begin itemize

• Dòng đầu chứa hai số nguyên dương \(N\) và \(M\) \((1 \le N \le 10^5,\ 1 \le M \le 10^9)\).

• \(N\) dòng tiếp theo, dòng thứ \(i\) chứa hai số nguyên dương \(s_i\) và \(e_i\) \((1 \le s_i, e_i \le 10^9)\).

\OutputFile
In ra một số nguyên duy nhất là chỉ số sức mạnh lớn nhất có thể đạt được.

Subtasks

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

Example

3 4
2 2
2 5
5 1

23