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ủ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ó hai 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 nhậ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 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ủa bạn nhận được một 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.

Dữ liệu vào từ tệp văn bản TROCHOI.INP:

• Dòng đầu tiên chứa hai 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 hai số nguyên dương $s_i$ và $e_i$ ($s_i \le 10^9, e_i \le 10^9$).

Kết quả ghi ra tệp văn bản TROCHOI.OUT:

• Một số nguyên dương 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.

• Có 40% số test tương ứng 40% số điểm có $M = 2$.
• 40% số test tương ứng 40% số điểm có $M \le 100$.
• 20% số test còn lại tương ứng 20% số điểm không có ràng buộc thêm.