안전한 베팅

원 위에 $N = 2K + 1$개의 칸이 놓인 룰렛이 있다. 칸의 개수 $N$은 항상 홀수이며, $i$번째 칸에는 가격 $c_i$가 매겨져 있다. 칸들은 원형으로 배열되어 있어 마지막 칸은 첫 번째 칸과 이웃한다.

한 번의 베팅은 원 위에서 연속한 $K$개의 칸을 덮으며, 그 베팅의 가격은 덮인 $K$개 칸의 가격을 모두 더한 값이다.

모든 칸을 빠짐없이 덮으려면 베팅을 정확히 세 번 해야 한다. $N = 2K + 1$이 홀수이므로 $K$개짜리 베팅 두 번으로는 항상 한 칸이 남아 전체를 덮을 수 없고, 세 번이면 (일부 칸이 두 번 덮이더라도) 전체를 덮을 수 있다.

세 번의 베팅으로 모든 칸을 덮을 때, 세 베팅 가격의 합이 최소가 되도록 하라. 여러 베팅에 동시에 덮인 칸은 그 칸을 덮은 베팅마다 각각 가격에 포함된다. 이 최소 합을 구하라.

입력에는 여러 개의 룰렛이 주어진다. 각 룰렛은 두 줄로 이루어진다.

첫째 줄에는 홀수 $N = 2K + 1$ ($3 \le N < 200\,000$), 즉 룰렛의 칸 수가 주어진다.

둘째 줄에는 원둘레를 따라 나타나는 순서대로 각 칸의 가격을 나타내는 $N$개의 정수 $c_0, c_1, \dots, c_{N-1}$ ($0 \le c_i \le 1000$)가 공백으로 구분되어 주어진다. 마지막 칸은 첫 번째 칸과 이웃한다.

마지막 룰렛 다음 줄에는 $0$ 하나만 주어지며, 이는 입력의 끝을 뜻한다.

각 룰렛마다 다음 조건을 모두 만족하는 베팅 집합의 최소 가격을 한 줄에 하나씩 출력한다.

1. 베팅은 정확히 세 번 한다.
2. 각 베팅은 연속한 $K$개의 칸을 덮는다.
3. 세 베팅이 함께 룰렛의 모든 칸을 덮는다 (일부 칸은 두 번 덮여도 된다).
4. 세 베팅 가격의 합이 가능한 모든 방법 중에서 최소이다.

베팅의 가격은 그 베팅이 덮는 각 칸의 가격을 더한 값이다.