Bạn đang chơi một trò chơi với ~n~ chiếc nút. Bạn có ~q~ lượt, và trong mỗi lượt bạn bấm đúng một chiếc nút. Khi bấm nút thứ ~i~, bạn nhận được ~s_i~ điểm. Ngoài ra, lần đầu tiên bấm nút thứ ~i~, bạn còn nhận thêm ~e_i~ điểm thưởng.

Một chiếc nút có thể được bấm bao nhiêu lần cũng được, nhưng điểm thưởng ~e_i~ chỉ được tính duy nhất một lần. Hãy tìm cách bấm các nút để tổng điểm đạt được là lớn nhất.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên ~n~ và ~q~.
• ~n~ dòng tiếp theo, mỗi dòng chứa hai số nguyên ~e_i~ và ~s_i~.

Kết quả

In ra một số nguyên là tổng điểm lớn nhất có thể đạt được.

Ví dụ

Đầu vào:

3 6
1 3
2 2
4 3

Đầu ra:

24

Giải thích: Bấm nút ~3~ một lần được ~3 + 4 = 7~, nút ~1~ một lần được ~3 + 1 = 4~, và nút ~2~ một lần được ~2 + 2 = 4~. Ba lượt đó cho ~15~ điểm. Dùng ~3~ lượt còn lại để bấm một nút bất kỳ có ~s_i = 3~, được thêm ~9~ điểm. Tổng cộng là ~24~.

Giới hạn

• ~1 \le n \le 10^6~
• ~1 \le q \le 10^9~
• ~1 \le s_i, e_i \le 10^6~

Lưu ý rằng ~q~ có thể lớn hơn hoặc nhỏ hơn ~n~ rất nhiều. Kết quả có thể lên tới khoảng ~10^{15}~, nên không vừa trong số nguyên 32 bit. Dữ liệu vào lớn — hãy dùng cách đọc dữ liệu nhanh.