Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

PTIT127H - Tấn công đường ray

Giữa những kho chứa (được gán trọng số từ 1 đến 5) có các đường ray nối. Giá trị chiến lược trên một đường ray được tính bằng tổng tất cả giá trị của các đoạn cộng lại. Ví dụ với đường ray được mô tả như sau: 

Thì giá trị chiến lược sẽ là: 4*5 + 4*1 + 4*2 + 5*1 + 5*2 + 1*2 = 49.

Giả sử người ta muốn tấn công một đoạn đường ray sao cho giá trị chiến lược còn lại là nhỏ nhất. Trong trường hợp trên nếu tấn công đoạn từ 5 đến 1 

thì giá trị chiến lược sẽ là: 4*5 + 1*2 = 22. Còn nếu tấn công đoạn 4 đến 5: 

thì giá trị sẽ chỉ là: 5*1 + 5*2 + 1*2 = 17. Đây là giá trị nhỏ nhất có thể. 

Input

Gồm nhiều bộ test, mỗi bộ test gồm hai số nguyên N và M (1<=N<=500 và 0<=M<n) trong đó N là số kho chứa trên đường ray và M là số lần tấn công. Dòng tiếp theo là N số nguyên dương từ 1 đến 5 theo thứ tự là trọng số các kho chứa trên đường.

Dữ liệu vào kết thúc với một dòng chứa 2 số 0.  

Output

ghi trên một dòng số nguyên dương là giá trị chiến lược nhỏ nhất có thể còn lại. 

Example

Input:

4 1

4 5 1 2

4 2

4 5 1 2

0 0
Output:

17

2

Được gửi lên bởi:adm
Ngày:2012-03-31
Thời gian chạy:1s
Giới hạn mã nguồn:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Ngôn ngữ cho phép:ASM32-GCC ASM32 MAWK BC C CSHARP C++ 4.3.2 CPP CPP14 COFFEE LISP sbcl DART FORTH GO JAVA JS-MONKEY JS-RHINO KTLN OCT PAS-GPC PAS-FPC PERL PERL6 PROLOG PYTHON PYTHON3 PY_NBC R RACKET SQLITE SWIFT UNLAMBDA

hide comments
2014-10-09 08:57:12 Black Hole
n^3 mãi mới AC,time chặt thật :3
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.