Chuồng bò vòng tròn

Xem PDF

Nộp bài


Điểm: 10 (thành phần)
Thời gian: 1.0s
Bộ nhớ: 500M

Tác giả:
Dạng bài

Sau siêu bão Noru, chuồng trâu của ngochuy bị hư nghiêm trọng. Sau khi sửa lại chuồng với anh thợ sửa ống nước BRUH, chuồng đã được sửa một cách trọn vẹn và được đổi sang chuồng phong cách châu Âu có hình dáng vòng tròn. Tuy rất vui với chuồng mới nhưng ngochuy vẫn phải lo lắng về việc phân bổ các chú trâu. Sau khi nghiên cứu tính cách của các chú trâu, ngochuy đã bày ra một cách sắp xếp hợp lý. Cụ thể, chuồng bao gồm một vòng gồm \(n\) phòng, được đánh số theo chiều kim đồng hồ từ \(1\ldots n\) xung quanh chu vi của chuồng \((3\leq n\leq 100)\). Mỗi phòng đều có cửa ra vào hai phòng bên cạnh, và cũng có cửa mở ra bên ngoài chuồng để các chú trâu từ ngoài đi vào.

ngochuy muốn chính xác \(r_i\) con trâu phải ở trong phòng \(i\ (1\leq r_i\leq 10^6)\). Để bầy trâu vào chuồng một cách trật tự, anh ta dự định mở \(k\) cửa ra bên ngoài của \(k\) chuồng \((1\leq k\leq 7)\), chỉ cho phép những con trâu từ bên ngoài đi vào qua những cánh cửa đó. Sau đó, mỗi con trâu đi theo chiều kim đồng hồ qua các phòng cho đến khi đến được điểm đến thích hợp. Nông dân ngochuy muốn mở khóa các cánh cửa bên ngoài sao cho những con trâu của anh ấy phải đi bộ chung một khoảng cách tối thiểu sau khi vào chuồng (ban đầu chúng có thể xếp hàng nhưng vì chúng thích bên ngoài \(k\) cửa không khóa; điều này không góp phần vào tổng khoảng cách trong câu hỏi). Hãy xác định tổng quãng đường tối thiểu mà con trâu của anh ta sẽ cần đi, nếu anh ta chọn \(k\) cửa tốt nhất để mở khóa.

INPUT:

  • Dòng đầu tiên của đầu vào chứa \(n\) và \(k\).
  • Mỗi dòng trong số \(n\) dòng còn lại chứa \(r_1, r_2,\ldots,\ r_n\).

OUTPUT:

  • Hãy viết quãng đường tối thiểu mà con trâu đi được.

SAMPLE INPUT:

6 2
2
5
4
2
6
2

SAMPLE OUTPUT:

14

Giải thích: ngochuy có thể mở cửa \(2,\ 5\).

Credits: Brian Dean