← 返回题目列表

Codeforces · 1401/B

B. 三元序列

中文机器翻译题面 查看原题

给定两个序列 $$$a_1, a_2, \dots, a_n$$$ 和 $$$b_1, b_2, \dots, b_n$$$。两个序列的每个元素都是 $$$0$$$、$$$1$$$ 或 $$$2$$$。序列$$$a$$$中的元素个数$$$0$$$、$$$1$$$、$$$2$$$分别为$$$x_1$$$、$$$y_1$$$、$$$z_1$$$,序列$$$b$$$中的元素个数$$$0$$$、$$$1$$$、$$$2$$$为分别为$$$x_2$$$、$$$y_2$$$、$$$z_2$$$。

您可以根据需要重新排列 $$$a$$$ 和 $$$b$$$ 序列中的元素。之后,我们定义一个序列$$$c$$$,如下所示:

$$$c_i = \begin{cases} a_i b_i & \mbox{if }a_i > b_i \\ 0 & \mbox{if }a_i = b_i \\ -a_i b_i & \mbox{if }a_i < b_i \end{cases}$$$

您希望使 $$$\sum_{i=1}^n c_i$$$ (序列 $$$c$$$ 中所有元素的总和)尽可能大。最大可能的总和是多少?

输入

第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。

每个测试用例由两行组成。每个测试用例的第一行包含三个整数 $$$x_1$$$、$$$y_1$$$、$$$z_1$$$ ($$$0 \le x_1, y_1, z_1 \le 10^8$$$) — 序列 $$$a$$$ 中 $$$0$$$-s、$$$1$$$-s 和 $$$2$$$-s 的数量。

每个测试用例的第二行还包含三个整数 $$$x_2$$$, $$$y_2$$$, $$$z_2$$$ ($$$0 \le x_2, y_2, z_2 \le 10^8$$$; $$$x_1 + y_1 + z_1 = x_2 + y_2 + z_2 > 0$$$) — 序列 $$$b$$$ 中 $$$0$$$-s、$$$1$$$-s 和 $$$2$$$-s 的数量。

输出

对于每个测试用例,打印序列 $$$c$$$ 的最大可能总和。

示例

输入 #1

3
2 3 2
3 3 1
4 0 1
2 3 0
0 0 1
0 0 1

输出 #1

4
2
0

注意

在第一个示例中,最佳解决方案之一是:

$$$a = \{2, 0, 1, 1, 0, 2, 1\}$$$

$$$b = \{1, 0, 1, 0, 2, 1, 0\}$$$

$$$c = \{2, 0, 0, 0, 0, 2, 0\}$$$

在第二个示例中,最佳解决方案之一是:

$$$a = \{0, 2, 0, 0, 0\}$$$

$$$b = \{1, 1, 0, 1, 0\}$$$

$$$c = \{0, 2, 0, 0, 0\}$$$

在第三个示例中,唯一可能的解决方案是:

$$$a = \{2\}$$$

$$$b = \{2\}$$$

$$$c = \{0\}$$$