You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

题目描述

小 Y 的朋友小 Z 带她去爬山。

小 Y 对此做好了充足的准备，她把登山用的食物装进了 $3$ 个背包里，第 $i$（$i\in\{1,2,3\}$）个背包里有 $a_i$ 份食物。

在每个白天，若第 $i$ 个背包尚未被丢弃，小 Y 会因背负它而花费 $b_i$ 点体力，这一花费与背包中剩余的食物数量无关。

在第 $k$ 天夜晚，小 Y 需要选择一个未被丢弃的背包。

• 如果背包里剩余的食物 $\le k$ 份，那么小 Y 和小 Z 会把食物吃完后直接把背包丢掉。
• 否则，小 Y 和小 Z 会吃掉背包里的 $k$ 份食物。

如果某天晚上，三个背包都被丢弃了，那么小 Y 和小 Z 就会立刻结束登山。

小 Y 想让你规划每天夜晚选择哪个背包，才能使从登山开始到结束所花费的体力总和最小。

小 Y 想准备得更全面，所以她准备了 $q$ 个计划，每个计划中都会给出三个背包的 $a_1,a_2,a_3,b_1,b_2,b_3$，她想让你对每个计划都计算出花费体力之和的最小值，注意各个计划之间相互独立。

输入格式

从文件 climb.in 中读入数据。

第一行一个整数 $q$，表示计划的数量。

第 $i+1$（$1\le i\le q$）行六个整数 $a_1,a_2,a_3,b_1,b_2,b_3$，表示第 $i$ 个计划中三个背包的食物数量以及每天携带需要花费的体力。

输出格式

输出到文件 climb.out 中。

输出 $q$ 行，第 $i$（$1\le i\le q$）行的整数表示第 $i$ 个计划中花费体力的最小值。

样例 1 输入

1
5 6 8 6 7 5

样例 1 输出

81

样例 1 解释

按照 $(2,2,2,3,1,3)$ 的顺序选择每天晚上使用的背包，花费为 $18\times 3+11\times 2+5=81$。

样例 2

见选手目录下的 climb/climb2.in 与 climb/climb2.ans。

该样例满足子任务 $1$ 的约束条件。

样例 3

见选手目录下的 climb/climb3.in 与 climb/climb3.ans。

该样例满足子任务 $2$ 的约束条件。

样例 4

见选手目录下的 climb/climb4.in 与 climb/climb4.ans。

该样例满足子任务 $3$ 的约束条件。

样例 5

见选手目录下的 climb/climb5.in 与 climb/climb5.ans。

该样例满足子任务 $4$ 的约束条件。

样例 6

见选手目录下的 climb/climb6.in 与 climb/climb6.ans。

该样例满足子任务 $5$ 的约束条件。

样例 7

见选手目录下的 climb/climb7.in 与 climb/climb7.ans。

该样例满足子任务 $6$ 的约束条件。

数据范围

对于所有测试数据，保证 $1\le q\le 50$，$1\le a_1,a_2\le 100$，$1\le a_3\le 10^{18}$，$1\le b_1,b_2,b_3\le 10^9$。

本题开启所有合理的子任务依赖。