Description

Dilpreet wants to paint his dog- Buzo's home that has n boards with different lengths[A1, A2,..., An]. He hired k painters for this work and each painter takes 1 unit time to paint 1 unit of the board.The problem is to find the minimum time to get this job done under the constraints that any painter will only paint continuous sections of boards, say board {2, 3, 4} or only board {1} or nothing but not board {2, 4, 5}.

Constraints:1<=T<=100,1<=k<=30,1<=n<=50,1<=A[i]<=500

Input

The first line consists of a single integer T, the number of test cases. For each test case, the first line contains an integer k denoting the number of painters and integer n denoting the number of boards. Next line contains n- space separated integers denoting the size of boards

Output

For each test case, the output is an integer displaying the minimum time for painting that house.

Sample Input 1

2
2 4
10 10 10 10
2 4
10 20 30 40

Sample Output 1

20
60

Solution

import math
# 求数组从begin到end的和
def list_sum(a, begin, end):
    sum = 0
    for i in range(begin,end+1):
        sum += a[i]
    return sum


def find_min_time(k, n, a):
    dp = [[0 for i in range(n+1)] for j in range(k+1)]
    # 只有有一个油漆工
    for i in range(1,n+1):
        dp[1][i] = list_sum(a,0,i-1)
    # 只有一块板
    for i in range(1,k+1):
        dp[i][1] = a[0]
    for i in range(2,k+1):
        for j in range(2,n+1):
            min_time = math.inf
            for p in range(1,j+1):
                # 求k个人j个板子的划分，需要求出前k-1个人涂p个板子时间和第k个人涂第p+1到最后的板子的时间的最小值
                min_time = min(min_time,max(dp[i-1][p], list_sum(a, p, j-1)))
            dp[i][j] = min_time
    return dp[k][n]


if __name__ == '__main__':
    T = int(input())
    while T:
        T -= 1
        k,n = map(int, input().split())
        a = list(map(int, input().split()))
        print(find_min_time(k, n, a))