CF2216B THU Packing Puzzle

有三种类型的二维方块：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 > 0$），分别表示三种形状的方块数量。

对于每组测试用例，输出一个整数，表示 $n$ 的最小可能值。

前面三个测试用例的最优解排列如下所示：  由 ChatGPT 5 翻译