Danh sách phát

Bạn có một danh sách phát gồm $n$ bài hát. Bài hát thứ $i$ có độ dài $t_i$ và độ hay $b_i$.

Khi nghe một tập hợp các bài hát, độ thích thú thu được bằng tổng độ dài của các bài hát trong tập nhân với độ hay nhỏ nhất trong số đó. Chẳng hạn, nghe $3$ bài hát có độ dài $[5,7,4]$ và độ hay $[11,14,6]$ cho độ thích thú $(5+7+4)·6=96$.

Hãy chọn không quá $k$ bài hát từ danh sách sao cho độ thích thú thu được là lớn nhất. Lưu ý rằng chọn ít hơn $k$ bài hát là hoàn toàn được phép, và đôi khi còn tốt hơn: thêm một bài hát dở vào tập có thể kéo tụt độ hay nhỏ nhất và làm giảm kết quả.

Dữ liệu vào

• Dòng đầu tiên chứa hai số nguyên $n$ và $k$ — số bài hát trong danh sách và số bài hát tối đa được chọn.
• $n$ dòng tiếp theo, dòng thứ $i$ chứa hai số nguyên $t_i$ và $b_i$ — độ dài và độ hay của bài hát thứ $i$.

Dữ liệu ra

In ra một số nguyên duy nhất — độ thích thú lớn nhất có thể đạt được.

Ràng buộc

• $1\le k\le n\le 3·{10}^5$
• $1\le t_i,b_i\le {10}^6$

Ví dụ