• 파일 합치기에서 n의 제한을 늘린 버전.
• 풀이는 최적 이진 검색 트리를 참고. 여기에서는 Garsia–Wachs algorithm을 적용해서 O(n^2)으로 구현했다.
• 크누스 최적화를 사용해서 푼 코드는 파일 합치기를 참고

"""Solution code for "BOJ 13974. 파일 합치기 2".

- Problem link: https://www.acmicpc.net/problem/13974
- Solution link: http://www.teferi.net/ps/problems/boj/13974
"""

import itertools
import sys

INF = float('inf')


def insert_rec(size, pos, l):
    cost = 0
    while len(l) + pos > 2 and size >= l[pos - 2]:
        new_size = l.pop(pos - 1) + l.pop(pos - 1)
        new_pos = next(x for x in range(pos - 1, -(len(l) + 1), -1)
                       if l[x] >= new_size) + 1
        cost += new_size + insert_rec(new_size, new_pos, l)
    if pos == 0:
        l.append(size)
    else:
        l.insert(pos, size)
    return cost


def main():
    T = int(sys.stdin.readline())
    for _ in range(T):
        K = int(sys.stdin.readline())  # pylint: disable=unused-variable
        file_sizes = [int(x) for x in sys.stdin.readline().split()]

        l = [INF]
        cost = 0
        for size in itertools.chain(file_sizes, [INF]):
            cost += insert_rec(size, 0, l)

        print(cost)


if __name__ == '__main__':
    main()