Màn cuối của lễ khai mạc IOI 2015 đang diễn ra. Trong lễ khai mạc, mỗi đội lẽ ra được nhận một hộp quà lưu niệm từ nước chủ nhà. Tuy nhiên, các tình nguyện viên mải mê theo dõi buổi lễ đến mức quên mất quà lưu niệm. Người duy nhất còn nhớ là Aman. Là một tình nguyện viên nhiệt tình và mong muốn IOI diễn ra hoàn hảo, anh muốn chuyển hết quà cho các đội trong thời gian ngắn nhất.

Địa điểm tổ chức lễ khai mạc là một vòng tròn được chia thành \(L\) khoang giống nhau. Các khoang được đánh số liên tiếp quanh vòng tròn từ \(0\) đến \(L-1\). Với \(0 \le i \le L-2\), khoang \(i\) kề khoang \(i+1\); khoang \(0\) cũng kề khoang \(L-1\). Có \(N\) đội tại đây, mỗi đội ngồi trong một khoang. Một khoang có thể chứa số đội tùy ý; cũng có thể không có đội nào.

Có \(N\) phần quà giống nhau. Ban đầu, Aman và tất cả phần quà đều ở khoang \(0\). Aman phải phát cho mỗi đội một phần quà, rồi quay về khoang \(0\) sau khi phát phần quà cuối cùng. Lưu ý rằng có thể có đội ngồi ngay tại khoang \(0\).

Tại mọi thời điểm, Aman chỉ mang được tối đa \(K\) phần quà. Anh phải lấy quà ở khoang \(0\) và việc lấy quà không tốn thời gian. Mỗi phần quà phải được mang theo cho đến khi được trao cho một đội. Khi mang theo ít nhất một phần quà và đến khoang có đội chưa nhận quà, Aman có thể trao cho đội đó một phần quà mình đang mang. Việc trao quà cũng không tốn thời gian. Chỉ việc di chuyển mới tốn thời gian: Aman có thể đi quanh vòng tròn theo cả hai chiều; mỗi lần sang một khoang kề, theo chiều kim đồng hồ hoặc ngược chiều kim đồng hồ, mất đúng một giây, bất kể đang mang bao nhiêu phần quà.

Hãy tìm số giây ít nhất để Aman phát hết quà rồi trở về vị trí ban đầu.

Ví dụ

Có \(N=3\) đội, Aman mang được \(K=2\) phần quà, và có \(L=8\) khoang. Các đội ngồi ở các khoang \(1\), \(2\) và \(5\).

Hình minh họa một phương án tối ưu. Trong chuyến đầu, Aman lấy hai phần quà, phát một phần cho đội ở khoang \(2\), phần còn lại cho đội ở khoang \(5\), rồi trở về khoang \(0\). Chuyến này mất \(8\) giây. Trong chuyến thứ hai, anh mang phần quà còn lại đến đội ở khoang \(1\), rồi quay về khoang \(0\), mất thêm \(2\) giây. Tổng thời gian là \(10\) giây.

Chi tiết cài đặt

Cài đặt hàm sau trong C hoặc C++, sử dụng header dùng chung boxes.h:

long long delivery(int N, int K, int L, int p[]);

Trong Java, cài đặt phương thức sau trong lớp boxes:

public long delivery(int N, int K, int L, int[] p)

Tham số p trong tệp mẫu chính thức chính là mảng positions được mô tả dưới đây; tên tham số không ảnh hưởng đến giao diện.

• Hàm delivery được chương trình chấm gọi đúng một lần.
• N: số đội.
• K: số phần quà tối đa Aman có thể mang cùng lúc.
• L: số khoang tại địa điểm tổ chức lễ khai mạc.
• positions: mảng có \(N\) phần tử; positions[0], ..., positions[N-1] là số hiệu khoang của các đội. Các phần tử được sắp theo thứ tự không giảm và thuộc đoạn \([0,L-1]\).
• Hàm trả về số giây ít nhất để Aman hoàn thành việc phát quà và quay về khoang \(0\). Kết quả dùng kiểu số nguyên 64 bit.

Chỉ nộp phần cài đặt hàm, không viết main. C và C++ đều dùng #include "boxes.h"; LQDOJ cung cấp cùng tên header cho cả hai ngôn ngữ. Java dùng lớp boxes, không viết phương thức main.

Phân nhóm

Mỗi subtask được trọn số điểm nếu tất cả các test thuộc subtask đều đúng; nếu không, subtask được \(0\) điểm. Các test mẫu là pretest \(0\) điểm.

Chương trình chấm mẫu

Chương trình chấm mẫu đọc dữ liệu theo định dạng:

• Dòng \(1\): N K L.
• Dòng \(2\): positions[0] ... positions[N-1].

Chương trình in giá trị trả về của delivery. Gói đính kèm dùng các tệp boxes.in và boxes.out; bộ chấm LQDOJ đã chuyển phần đọc/ghi của grader sang đầu vào/đầu ra chuẩn, không thay đổi giao diện hàm.

Dữ liệu vào:

3 2 8
1 2 5

Kết quả:

10