提示: 欢迎访问OurACM平台。
Problem 2302 Necklace

Accept: 14    Submit: 127
Time Limit: 3000 mSec    Memory Limit : 524288 KB

Problem Description

Xzz is a child with severe procrastinations. The new semester begins, He still has a lot of homework to do. Now there are K friends help him finish his homework. Xzz has a necklace with n pearl. Now he want to Split into k parts, and send them to these k friends. Each friend will have a value representative how happy they are. And the value is equal the square of sum of the pearl in one part. Now Xzz wants to know minimum sum of his k friends value.

Input

First line of the input file contains an integer T(0 < T ≤ 20) that indicates how many cases of inputs are there.

The description of each case is given below:

The first line of each case contains two numbers n, k, means there is n pearl necklace and k friends. n, k ≤ 200

Then follow n lines. In ith line there will be n numbers, ai, means the value of ith pearl.1 ≤ ai ≤ 100

Output

One integer means the minimum sum of his k friends value.

Sample Input

2 3 3 1 2 3 5 3 5 2 3 8 2

Sample Output

14 138

Hint

Each part must be continuous at necklace.

Case 2, three parts are {2, 3}, {8}, {5, 2}

(2 + 3)^2 + 8^2 + (2 + 5)^2

Source

第九届福建省大学生程序设计竞赛-重现赛(感谢承办泉州师范学院)

Submit  Back  Status  Discuss