n được lắp đặt hệ thống tưới tiêu. Chỉ có một đội kỹ thuật, nên các trang trại được phục vụ lần lượt theo một thứ tự nào đó.

Với mỗi trang trại ~i~:

• ~t_i~ là thời gian lắp đặt.
• ~p_i~ là thiệt hại phải chịu trên mỗi ngày chờ.

Có ~K~ suất lắp đặt cao cấp. Những trang trại nhận suất này sẽ được đưa lên đầu lịch trình, theo thứ tự tối ưu giữa chính chúng. Các trang trại còn lại được phục vụ sau đó, cũng theo thứ tự tối ưu giữa chính chúng.

Gọi ~S = \sum_{i=1}^{N} t_i~. Hệ số ưu tiên của trang trại ~i~ được xác định bởi:

~p_i \cdot (S - t_i)~.

Tổng thiệt hại của một trang trại bằng ~p_i~ nhân với thời điểm hoàn thành lắp đặt của trang trại đó.

Yêu cầu

Chọn đúng ~K~ trang trại để đưa vào nhóm ưu tiên sao cho tổng thiệt hại của tất cả các trang trại là nhỏ nhất.

Dữ liệu

• Dòng ~1~ chứa hai số nguyên ~N, K~.
• Dòng ~2~ chứa ~N~ số nguyên dương ~t_1, t_2, \dots, t_N~.
• Dòng ~3~ chứa ~N~ số nguyên dương ~p_1, p_2, \dots, p_N~.

Kết quả

In ra một số nguyên duy nhất là tổng thiệt hại nhỏ nhất.

Ví dụ

Ví dụ 1

Input

4 2
6 2 7 4
3 9 2 7

Output

134

Giải thích

Ví dụ 1

Chọn hai trang trại ~2~ và ~4~ vào nhóm ưu tiên. Khi đó một lịch trình tối ưu là ~[2,4,1,3]~.

Tổng thiệt hại là:

~9 \cdot 2 + 7 \cdot (2+4) + 3 \cdot (2+4+6) + 2 \cdot (2+4+6+7) = 134~.

Ràng buộc và chấm điểm

Ràng buộc

• ~1 \le N, K \le 10^5~.
• ~1 \le t_i \le 10^6~.
• ~1 \le p_i \le 10^9~.

Chấm điểm

• Subtask ~1~: ~25\%~ số điểm, ~N \le 10~, ~K \le 5~, ~1 \le t_i \le 10^2~, ~1 \le p_i \le 10^2~.
• Subtask ~2~: ~30\%~ số điểm, ~N \le 10^2~, ~K \le 20~, ~1 \le t_i \le 10^3~, ~1 \le p_i \le 10^6~.
• Subtask ~3~: ~45\%~ số điểm, không có ràng buộc bổ sung.