Vua Hùng thứ I cai trị đất nước Văn Lang hết mực yêu thương dân. Với chính sách cấp gạo cho người dân theo nhu cấu sử dụng, nhà Vua đã ra lệnh cho các quan xây dựng một số điểm cấp gạo để thuận tiện cho người dân đi nhận gạo. Người dân đất nước Văn Lang sinh sống thành từng làng dọc theo một trục đường chính (mà ta coi như một trục tọa độ), có tất cả làng đánh số từ đến , làng thứ có tọa độ là số nguyên và có số dân là số nguyên dương . Nhà Vua muốn xây dựng điểm cấp gạo, mỗi điểm cấp gạo sẽ nằm ở làng nào đó (để tiện cho việc trông coi, bảo vệ kho gạo). Người dân khi đi nhận gạo, gần điểm cấp gạo nào sẽ tới điểm cấp gạo đó, độ vất vả của mỗi người dân sẽ bằng khoảng cách từ làng họ sống đến điểm cấp gạo gần làng đó nhất. Độ vất vả của cả đất nước sẽ bằng tổng độ vất vả của mỗi người dân.
Nhà Vua rất thương dân nên muốn xây dựng k điểm cấp gạo sao cho độ vất vả của cả đất nước là nhỏ nhất có thể.
Yêu cầu: Tính toán độ vất vả của cả đất nước Văn Lang nếu xây dựng điểm cấp gạo hợp lý nhất.
Dữ liệu vào:
Dòng đầu chứa hai số nguyên dương và ;
Dòng thứ hai nghi số nguyên ;
Dòng thứ ba nghi số nguyên dương .
Hai số liên tiếp trên một dòng được ghi cách nhau một dấu cách.
Dữ liệu ra:
Ghi ra một số nguyên duy nhất là độ vất vả nhỏ nhất của đất nước Văn Lang.
Ví dụ:
Dữ liệu vào:
4 2
1 2 3 5
1 2 2 3
Dữ liệu ra:
3
Giải thích:
Hai điểm cấp gạo được đặt ở ngôi làng số và số . Người dân ở các ngôi làng số sẽ đến điểm cấp gạo số nhận gạo (độ vất vả là ), người dân ở ngôi làng số sẽ nhận gạo ở điểm cấp gạo số . Tổng độ vất vả là .
