토지 분할 세금

International Concrete Projects Company(ICPC)는 고급 주택 시장을 전문으로 하는 건설 회사입니다. ICPC는 호수 주변에 새 주택 단지를 계획하고 있습니다. 지어질 필지들은 크기가 서로 다르지만 모두 호숫가에 접해 있으며, 각 필지는 단지 안에서 정확히 두 개의 이웃(왼쪽 하나, 오른쪽 하나)을 가집니다. 따라서 필지들은 호수를 둘러싸는 하나의 고리(원형) 형태로 배치됩니다.

ICPC는 호수 주변의 토지를 소유하고 있으며, 이를 계획에 따라 여러 필지로 나누어야 합니다. 그런데 County Council(군 의회)은 작은 필지가 남발되는 것을 막기 위해 다음과 같은 토지세 규정을 두고 있습니다.

1. 토지는 오직 일련의 '분할' 연산을 통해서만 나눌 수 있다.
2. 한 번의 분할은 하나의 토지 조각을 두 개의 조각으로 나누는 연산이다.
3. 분할을 할 때마다 세금을 내야 한다.

한 번의 분할로 생긴 두 조각 중 넓은 쪽의 넓이를 $A$라 하면, 그 분할에 대한 세금은 $A \times F$입니다. 여기서 $F$는 County Council이 매년 정하는 분할 세금 계수입니다. 규정 (2) 때문에 하나의 조각을 $N$개의 필지로 나누려면 $N - 1$번의 분할이 필요하고, 따라서 $N - 1$번 세금을 내야 합니다.

예를 들어 계수가 $2.5$이고, 호수를 따라 순서대로 놓인 필지들의 넓이가 $300, 100, 500, 100, 100, 200$이라고 합시다. 첫 분할에서 넓이 $500$인 필지를 나머지 전부에서 떼어내면, 넓은 쪽의 넓이가 $800$이므로 세금은 $2.5 \times (300 + 200 + 100 + 100 + 100)$입니다. 이어서 넓이 $300$인 필지를 그 이웃인 넓이 $100$짜리 필지와 함께 나머지에서 떼어내면 추가로 $2.5 \times (300 + 100)$을 냅니다. 이런 식으로 계속됩니다. 규정 (2) 때문에 불가능한 분할도 있습니다. 위 첫 분할 이후에는 넓이 $300$인 필지와 넓이 $200$인 필지를 나머지 세 필지에서 한 번에 떼어낼 수 없는데, 그렇게 하면 조각이 두 개보다 많아지기 때문입니다.

호수 주변 모든 필지의 넓이와 현재의 분할 세금 계수가 주어질 때, 계획대로 토지를 나누는 데 필요한 최소 총 분할 세금을 구하는 프로그램을 작성하세요.

입력은 여러 개의 테스트 케이스로 이루어집니다. 각 테스트 케이스의 첫 줄에는 필지의 수를 나타내는 정수 $N$과 분할 세금 계수를 나타내는 실수 $F$가 주어집니다($1 \le N \le 200$이고, $F$는 소수점 이하 두 자리로 주어지며 $0 < F \le 5.00$). 둘째 줄에는 계획상 이웃한 필지들의 넓이를 나타내는 $N$개의 정수 $X_i$가 주어집니다($1 \le i \le N$에 대해 $0 < X_i \le 500$). 필지 $X_k$는 $1 \le k \le N - 1$에 대해 $X_{k+1}$과 이웃하고, $X_N$은 $X_1$과 이웃합니다(즉 필지들은 원형으로 배치됩니다). 입력의 끝은 $N = F = 0$인 줄로 표시됩니다.

각 테스트 케이스마다 한 줄에 최소 총 분할 세금을 소수점 이하 두 자리의 실수로 출력하세요.