ABA12C.py

num_tc = int(raw_input())
for tc in xrange(0, num_tc):
    # Nhap dau vao
    N, K = map(int, raw_input().split())

    price = [0] * (K + 1)
    price[1:K+1] = map(int, raw_input().split())

    # Khoi tao so tien nho nhat de mua i kg tao
    # la so tien de mua 1 goi i Kg tao

    min_price = [([0] * (N + 1)) for row in xrange(K + 1)]

    for i in xrange(1, K + 1):
        for j in xrange(1, N + 1):
            min_price[i][j] = price[i]

    for i in xrange(2, K + 1):
        for x in xrange(2, N + 1):
            for j in xrange(1, i):
                if min_price[j][x - 1] < 0 or price[i - j] < 0 :
                    continue

                temp = min_price[j][x - 1] + price[i - j]

                if min_price[i][x] < 0 or temp < min_price[i][x]:
                    min_price[i][x] = temp

    print min_price[K][N]