Trong một trò chơi huấn luyện thú, mỗi người chơi sẽ sở hữu một con thú và sẽ huấn luyện để con thú của mình có điểm sức mạnh lớn nhất. Người chơi có ~M~ phút huấn luyện con thú của mình:

• Có ~N~ kĩ năng người chơi có thể lựa chọn để huấn luyện cho con thú;
• Mỗi phút huấn luyện kĩ năng thứ ~i~, con thú sẽ được tăng thêm ~e_i~ điểm sức mạnh (có thể lựa chọn huấn luyện một kĩ năng nhiều lần);
• Với kĩ năng thứ ~i~ mà con thú được huấn luyện lần đầu, con thú sẽ được tăng thêm ~s_i~ điểm sức mạnh.

Yêu cầu: Hãy lên phương án huấn luyện trong ~M~ phút để điểm sức mạnh của con thú là lớn nhất.

Input

• Dòng đầu tiên chứa hai số nguyên dương ~N, M~ (~1 \le N \le 10^5~; ~1 \le M \le 10^9~) là số lượng kĩ năng và thời gian huấn luyện cho thú;
• ~N~ dòng sau, dòng thứ ~i~ chứa hai số nguyên dương ~s_i~, ~e_i~ (~s_i, e_i \le 10^6~; ~1 \le i \le N~) là điểm sức mạnh được tặng khi huấn luyện kĩ năng lần đầu và điểm sức mạnh của kĩ năng.

Output

Số điểm sức mạnh tối đa có thể đạt được.

Sample Input 1

3 4
2 2
2 5
5 1

Sample Output 1

23

Giải thích: Huấn luyện kĩ năng 2 trong 3 phút và kĩ năng 3 trong 1 phút. Tổng điểm sức mạnh:

• Huấn luyện kĩ năng 2 trong 3 phút: ~2 + 5 \times 3 = 17~;
• Huấn luyện kĩ năng 3 trong 1 phút: ~5 + 1 \times 1 = 6~; Tổng điểm sức mạnh đạt được: ~17 + 6 = 23~.

Subtasks

• Có 40% số test ứng với 40% số điểm thoả mãn: ~M = 2~;
• 40% số test khác ứng với 40% số điểm thoả mãn: ~M \le 100~;
• 20% số test còn lại ứng với 20% số điểm không có ràng buộc gì thêm.