题目描述

假设你有许多扑克牌。如你所知，每张扑克牌的点数范围是从 $1$ 到 $13$。你需要使用这些扑克牌，在图 1 所示的纸板上玩一个游戏。游戏从一个名为 START 的位置开始。从 START 出发，你可以向左或向右走到一个矩形格子。每个格子都标有一个整数，该整数表示该格子到 START 的距离。

图 1：扑克牌游戏纸板

在这些格子上放置扑克牌时，你必须遵循以下规则：

1. 如果你将一张点数为 $n$ 的扑克牌放在标有数字 $i$ 的格子上，你将获得 $(n \times i)$ 分。
2. 一旦你在某个格子 $b$ 上放置了一张扑克牌，你就会挡住通向格子 $b$ 后面格子的路径。例如，在图 2 中，玩家将一张 “Q”（点数为 $12$）放在距离为 $1$ 的右侧格子上，他获得了 $1 \times 12$ 分，但这张 “Q” 也挡住了通向它后面格子的路径；也就是说，不允许再在它后面的格子上放置扑克牌了。

图 2：放置一张 “Q”

你的目标是：给定若干张扑克牌，找到一种放置方法，使你获得的总分数最小。例如，假设你有 $3$ 张牌，点数分别为 $5$、$10$ 和 “K”（点数为 $13$）。为了获得最小分数，你可以像图 3 那样放置扑克牌，此时总分数为 $1 \times 13 + 2 \times 5 + 2 \times 10 = 43$。

图 3：一个放置扑克牌的示例

输入

输入文件的第一行包含一个整数 $n$（$n \leq 10$），表示测试用例的数量。在每个测试用例中，首先是一个整数 $m$（$m \leq 100000$），表示扑克牌的数量。接下来，依次列出每张扑克牌的点数。注意，“A”、$2$、$3$、$\cdots$、“K” 的点数分别用整数 $1$、$2$、$3$、$\cdots$、$13$ 表示。每个测试用例的最终最小分数小于 $5000000$。

输出

逐行列出每个测试用例的最小分数。

输入样例

3
3
5 10 13
4
3 4 5 5
5
7 7 10 11 13

输出样例

43
34
110

题目来源

台湾 2002 年竞赛题目