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 ≤ i ≤ 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.

Input

- Dòng đầu tiên chưa hai số nguyên dương N và M (1 ≤ N ≤ 10⁵; 1 ≤ M ≤ 10⁹)
- 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, e_i ≤ 10⁹)

Output

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

Ràng buộc:

- 40% test có M = 2
- 40% test có M ≤ 100
- 20% test không có ràng buộc gì thêm

Ví dụ:

Input:

3 4
2 2
2 5
5 1

Output:

23

Giải thích:
Các 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