← 返回题目列表

Codeforces · 1945/A

A. 建立营地

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

组委会计划在参观结束后带奥赛参赛者徒步旅行。目前,需要占用的帐篷数量正在计算中。据了解,每个帐篷最多可容纳 $$$3$$$ 人。

参与者中,有 $$$a$$$ 内向者、$$$b$$$ 外向者和 $$$c$$$ 通用者:

- 每个内向的人都想独自住在帐篷里。因此,一个内向者的帐篷必须只容纳一个人——只有内向者本人。
- 每个外向的人都想和另外两个人一起住在一个帐篷里。因此,外向者的帐篷必须恰好容纳三个人。
- 每个通用都可以选择任何选项(独自生活、与另一个人一起生活或与另外两个人一起生活)。

组委会非常尊重每一位参赛者的意愿,所以他们希望能够全部实现。

请告诉我们需要带的最少帐篷数量,以便所有参与者都能根据自己的喜好容纳。如果无法以满足所有愿望的方式容纳参与者,则输出$$$-1$$$。

输入

每个测试由多个测试用例组成。第一行包含一个整数 $$$t$$$ ($$$1 \le t \le 10^4$$$) — 测试用例的数量。接下来是测试用例的描述。

每个测试用例由一行描述,其中包含三个整数 $$$a$$$、$$$b$$$、$$$c$$$ ($$$0 \le a, b, c \le 10^9$$$)——分别是内向者、外向者和共性者的数量。

输出

对于每个测试用例,输出一个整数 - 帐篷的最小数量,如果无法容纳参与者,则输出 $$$-1$$$。

示例

输入 #1

10
1 2 3
1 4 1
1 4 2
1 1 1
1 3 2
19 7 18
0 0 0
7 0 0
0 24 0
1000000000 1000000000 1000000000

输出 #1

3
-1
3
-1
3
28
0
7
8
1666666667

注意

在第一个测试用例中,$$$1$$$ 帐篷将提供给内向者,$$$1$$$ 帐篷将由两个外向者和一个通用者共享,最后一个帐篷将由两个通用者共享。总共需要 $$$3$$$ 帐篷。

在第二个测试用例中,三个外向者将乘坐 $$$1$$$ 帐篷,而一个内向者将乘坐 $$$1$$$ 帐篷。然后,就会剩下一名外向型和一名通用型。这个外向的人将无法与另外两个人一起生活。