Sau sự cố gần nhất liên quan đến chuồng tròn của Farmer John, người ta hẳn sẽ nghĩ rằng ông đã rút ra bài học về kiến trúc phi truyền thống. Tuy nhiên, ông cho rằng mình vẫn có thể khiến chuồng tròn (trong bài trước) hoạt động tốt bằng cách cho phép nhiều con bò vào mỗi phòng. Nhắc lại, chuồng gồm một vòng tròn có \(n\) phòng, được đánh số theo chiều kim đồng hồ từ \(1 \ldots n\) quanh chu vi chuồng (\(3 \leq n \leq 100\)). Mỗi phòng đều có cửa thông sang hai phòng bên cạnh và một cửa mở ra bên ngoài chuồng.

Farmer John muốn đúng \(r_i\) con bò ở lại trong phòng \(i\) (\(1 \leq r_i \leq 1\,000\,000\)). Để lùa bò vào chuồng một cách trật tự, ông dự định mở khóa \(k\) cửa ngoài (\(1 \leq k \leq 7\)), chỉ cho phép đàn bò đi vào qua các cửa đó. Sau đó, mỗi con bò đi theo chiều kim đồng hồ qua các phòng cho đến khi đến một vị trí thích hợp. Farmer John muốn mở khóa những cửa ngoài sao cho tổng quãng đường đàn bò phải đi sau khi vào chuồng là nhỏ nhất. Ban đầu, đàn bò có thể xếp hàng theo bất kỳ cách nào bên ngoài \(k\) cửa đã mở khóa; việc này không được tính vào tổng quãng đường đang xét. Hãy xác định tổng quãng đường nhỏ nhất mà đàn bò phải đi nếu ông chọn \(k\) cửa tốt nhất để mở khóa.

Dữ liệu vào

Dòng đầu tiên chứa \(n\) và \(k\). Mỗi dòng trong \(n\) dòng còn lại lần lượt chứa \(r_1 \ldots r_n\).

Dữ liệu ra

In tổng quãng đường nhỏ nhất mà đàn bò phải đi.

Ví dụ

6 2
2
5
4
2
6
2

14

Nguồn

USACO 2016 February Contest, Gold - Circular Barn Revisited: https://usaco.org/index.php?page=viewproblem2&cpid=622

Tác giả: Brian Dean.