← 返回题目列表

Codeforces · 2216/B

B. THU 包装拼图

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

二维块有三种类型:T 形、H 形和 U 形。它们的具体形状如下图所示:

给定三个非负整数$$$c_T$$$、$$$c_H$$$ 和$$$c_U$$$,分别代表T 形、H 形和U 形块的数量。您的任务是将所有 $$$(c_T + c_H + c_U)$$$ 块打包到 $$$n \times 3$$$ 网格中,遵循以下规则:

  • 每个方块必须完全放置在网格内;
  • 两个块不能重叠(即,任何单位单元不能被多个块覆盖);
  • 块可以是 已旋转 $$$90^{\circ}$$$ 的任意倍数,但它们的边缘必须保持与网格边界平行。

您必须找到存在这种包装的 $$$n$$$ 的最小可能值。

输入

每个测试包含多个测试用例。第一行包含测试用例的数量 $$$t$$$ ($$$1 \le t \le 10^4$$$)。测试用例的描述如下。

每个测试用例的唯一行包含三个整数 $$$c_T$$$、$$$c_H$$$ 和 $$$c_U$$$ ($$$0\le c_T,c_H,c_U\le 10^9$$$, $$$c_T+c_H+c_U \gt 0$$$) — T 形、H 形和分别为U形块。

输出

对于每个测试用例,输出一个整数 - $$$n$$$ 的最小可能值。

示例

输入
复制

5
1 1 1
2 0 0
1 1 0
0 0 1000000000
1000000000 1000000000 1000000000

输出
复制

7
5
5
3000000000
7000000000

注意

前三个测试用例的最佳解决方案如下: