Sau màn bão tán của đêm livestream cực hot, DoMixi quyết định tổ chức một buổi fan-meeting hoành tráng không kém. Địa điểm? Một sân khấu hình vòng tròn cực xịn với ~n~ khu vực chỗ ngồi, đánh số theo chiều kim đồng hồ từ ~1~ đến ~n~ xung quanh vòng.

DoMixi muốn khu vực thứ ~i~ có đúng ~r_i~ fan ngồi vào. Để kiểm soát an ninh, ban tổ chức chỉ mở ~k~ trong số ~n~ cổng vào. Mỗi fan vào từ một cổng được mở rồi đi theo chiều kim đồng hồ đến khu vực của mình — dù sao thì đi thêm một chút cũng để ngắm DoMixi lâu hơn mà!

Fan có thể xếp hàng bên ngoài các cổng theo thứ tự tùy ý, nhưng sau khi vào cổng thì chỉ được đi theo chiều kim đồng hồ.

Hãy giúp DoMixi chọn ~k~ cổng cần mở sao cho tổng số bước đi của tất cả mọi người là nhỏ nhất nhé!

Dữ liệu vào

Dòng đầu tiên chứa hai số nguyên ~n~ và ~k~ (~3 \le n \le 100~, ~1 \le k \le 7~).

~n~ dòng tiếp theo, dòng thứ ~i~ chứa số nguyên ~r_i~ (~1 \le r_i \le 10^6~) — số fan cần ngồi ở khu vực ~i~.

Kết quả

In ra một số nguyên duy nhất — tổng số bước đi tối thiểu.

Ví dụ

Đầu vào:

6 2
2
5
4
2
6
2

Đầu ra:

14

Giải thích: DoMixi mở cổng ~2~ và cổng ~5~. ~11~ fan vào từ cổng ~2~ đi tổng cộng ~8~ bước để vào khu vực ~2~, ~3~, ~4~. ~10~ fan vào từ cổng ~5~ đi tổng cộng ~6~ bước để vào khu vực ~5~, ~6~, ~1~.

Giới hạn

Trong tất cả các test: ~3 \le n \le 100~, ~1 \le k \le 7~, ~1 \le r_i \le 10^6~.