아라비아의 로렌스

T. E. 로렌스는 제1차 세계대전 당시 영국 장교로, 아랍 전사들을 이끌고 오스만 제국에 맞서 게릴라전을 벌였으며 주로 철도를 노렸다. 당신은 로렌스가 한정된 자원으로 최대한의 피해를 주도록 도와야 한다.

철도 노선은 완전히 직선이다. 분기점도 지선도 없다. 영국 정보부는 각 역(depot)에 1부터 5까지의 정수인 전략 가치를 부여한다. 역은 다른 역과 연결되어 있을 때에만 가치를 가진다. 철도 전체의 전략 가치는, 노선을 따라 직접 또는 간접적으로 여전히 연결되어 있는 모든 역 쌍에 대해 두 역의 전략 가치를 곱한 값을 모두 더한 것이다. 예를 들어:

이 철도의 전략 가치는 4 × 5 + 4 × 1 + 4 × 2 + 5 × 1 + 5 × 2 + 1 × 2 = 49이다.

로렌스는 정해진 횟수만큼만 공격할 수 있다. 그는 역을 직접 공격할 수 없으며(너무 잘 방어되어 있다), 각 공격은 사막 한가운데에서 인접한 두 역 사이의 철로를 파괴한다. 위 노선의 한가운데를 공격하면:

남은 전략 가치는 4 × 5 + 1 × 2 = 22이다. 대신 값이 4인 역과 5인 역 사이를 공격하면:

남은 전략 가치는 5 × 1 + 5 × 2 + 1 × 2 = 17이며, 이것이 이 경우 최선의 선택이다.

철도와 로렌스가 할 수 있는 공격 횟수가 주어질 때, 그가 철도에 남길 수 있는 전략 가치의 최솟값을 구하여라.

입력에는 여러 개의 데이터 집합이 있다. 각 데이터 집합은 두 정수 $N$과 $M$이 담긴 줄로 시작한다. $N$은 철도의 역 개수이고($1 \le N \le 500$), $M$은 로렌스가 자원을 가진 공격 횟수이다($0 \le M < N$). 다음 줄에는 $N$개의 정수가 있으며, 각각 1부터 5까지의 값으로 각 역의 전략 가치를 순서대로 나타낸다. 입력의 끝은 공백으로 구분된 두 개의 0이 담긴 줄로 표시된다.

각 데이터 집합마다 한 정수를 출력한다. 이는 로렌스가 공격을 한 뒤 철도에 남길 수 있는 전략 가치의 최솟값이다. 각 정수를 한 줄에 하나씩 출력하며, 출력 사이에 빈 줄을 넣지 않는다.