Hôm nay là sinh nhật của IOI-chan. Anh trai của cô bé, JOI-kun, đã đặt trước một chiếc bánh để chúc mừng. Tuy nhiên, cậu đặt nhầm \(N\) miếng bánh thay vì một chiếc bánh nguyên vẹn. Các miếng bánh được đánh số từ \(1\) đến \(N\). Miếng bánh thứ \(i\) có giá trị \(V_i\) và độ đậm màu \(C_i\).

JOI-kun quyết định chọn \(M\) miếng bánh khác nhau trong số \(N\) miếng và xếp chúng thành một vòng tròn. Gọi \(k_1, k_2, \ldots, k_M\) là chỉ số của các miếng bánh theo thứ tự trên vòng tròn, và đặt \(k_{M+1}=k_1\). Vẻ đẹp của cách sắp xếp được định nghĩa là

Hãy tính vẻ đẹp lớn nhất có thể đạt được bằng cách chọn và sắp xếp \(M\) miếng bánh.

Dữ liệu vào

Đọc từ đầu vào chuẩn theo định dạng:

N M
V_1 C_1
...
V_N C_N

Dữ liệu ra

In ra một dòng chứa một số nguyên: vẻ đẹp lớn nhất có thể đạt được.

Ràng buộc

• \(3 \le N \le 200\,000\).
• \(3 \le M \le N\).
• \(1 \le V_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• \(1 \le C_i \le 1\,000\,000\,000\) với \(1 \le i \le N\).
• Mọi giá trị trong dữ liệu vào đều là số nguyên.

Phân nhóm

1. \(5\) điểm: \(N \le 100\).
2. \(19\) điểm: \(N \le 2\,000\).
3. \(76\) điểm: Không có ràng buộc bổ sung.

Ví dụ

5 3
2 1
4 2
6 4
8 8
10 16

6

8 4
112103441 501365808
659752417 137957977
86280801 257419447
902409188 565237611
965602301 689654312
104535476 646977261
945132881 114821749
198700181 915994879

2323231661

Nguồn

JOI 2018/2019, trại huấn luyện mùa xuân, ngày thi thứ 4 (23/03/2019). Bản dịch tiếng Việt từ đề tiếng Anh chính thức của Ủy ban Olympic Tin học Nhật Bản. Trang công bố cấp phép nội dung theo CC BY-SA 4.0; bản dịch giữ cùng giấy phép.