Ngày Quốc tế Phụ nữ

Nhân ngày Quốc tế Phụ nữ, An muốn mua hoa tặng mẹ. An đi đến cửa hàng hoa gần nhà xem và chọn mua hoa. Tại cửa hàng có $n$ loại hoa khác nhau được đánh số từ 1 đến $n$ và số lượng hoa mỗi loại không giới hạn. Với mỗi loại hoa $i$, nếu mua 1 bông thì độ vui vẻ của mẹ An tăng lên $a_i$, còn nếu mua nhiều hơn 1 bông loại hoa này thì mỗi bông hoa tiếp theo sẽ làm độ vui vẻ của mẹ An tăng lên $b_i$. Tóm lại, nếu An mua $k > 0$ bông hoa loại $i$ thì độ vui vẻ của mẹ An sẽ tăng lên $a_i + (k - 1) \times b_i$.

An muốn chọn mua $m$ bông hoa từ $n$ loại hoa sao cho độ vui vẻ của mẹ An là nhiều nhất. Bạn hãy giúp An tính độ vui vẻ nhiều nhất của mẹ nếu chọn mua hoa một cách tối ưu.

Vào từ tệp văn bản flow.inp. Dòng thứ nhất chứa hai số nguyên $n, m$ ($1 \le n \le 10^5; 1 \le m \le 10^9$) tương ứng là số loại hoa trong cửa hàng và số bông hoa An cần mua. Dòng thứ $i$ trong $n$ dòng sau chứa hai số nguyên $a_i$ và $b_i$ ($0 \le a_i, b_i \le 10^9$) là thông tin của loại hoa thứ $i$ như mô tả ở trên.

Ghi ra tệp văn bản flow.out một số nguyên là độ vui vẻ nhiều nhất của mẹ An.

• Có 30% số test ứng với 30% số điểm thỏa mãn: $m = 1$ hoặc $a_1 = a_2 = \cdots = a_n$ hoặc $b_1 = b_2 = \cdots = b_n$;
• 40% số test khác ứng với 40% số điểm thỏa mãn: $1 \le n \le 10^3$;
• 30% số test còn lại ứng với 30% số điểm: Không có thêm ràng buộc nào.