小 X 在梦中进入了一个二维网格世界。
这个世界是由 的网格组成的，我们可以用坐标 来表示处于第i行第j列的网格，小 X 初始处于 位置的网格。
在这个世界里，小 X 只能向右或向下走，也就是说，当小 X 处于 网格时，小 X 只能前往 和 网格。
同时，小 X 还需要给他每个抵达过的网格（包括起点）交过路费，对于网格 ，过路费是 ，其中 和 是常数。
现在，小 X 想要前往位置 ，请你计算出小 X 要交的过路费总和最小是多少。
第一行三个整数 ， 表示数据组数，， 含义如题。
接下来一行 个整数，第 个数表示第 组数据对应的 。
行，每行一个整数，表示答案。
1 2 4 4
21
1 210 420 10
125
对于 的数据，。