311176: CF1945A. Setting up Camp
Description
The organizing committee plans to take the participants of the Olympiad on a hike after the tour. Currently, the number of tents needed to be taken is being calculated. It is known that each tent can accommodate up to $3$ people.
Among the participants, there are $a$ introverts, $b$ extroverts, and $c$ universals:
- Each introvert wants to live in a tent alone. Thus, a tent with an introvert must contain exactly one person — only the introvert himself.
- Each extrovert wants to live in a tent with two others. Thus, the tent with an extrovert must contain exactly three people.
- Each universal is fine with any option (living alone, with one other person, or with two others).
The organizing committee respects the wishes of each participant very much, so they want to fulfill all of them.
Tell us the minimum number of tents needed to be taken so that all participants can be accommodated according to their preferences. If it is impossible to accommodate the participants in a way that fulfills all the wishes, output $-1$.
InputEach test consists of multiple test cases. The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of test cases. This is followed by the descriptions of the test cases.
Each test case is described by a single line containing three integers $a$, $b$, $c$ ($0 \le a, b, c \le 10^9$) — the number of introverts, extroverts, and universals, respectively.
OutputFor each test case, output a single integer — the minimum number of tents, or $-1$ if it is impossible to accommodate the participants.
ExampleInput10 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 1000000000Output
3 -1 3 -1 3 28 0 7 8 1666666667Note
In the first test case, $1$ tent will be given to the introverts, $1$ tent will be shared by two extroverts and one universal, and the last tent will be shared by two universals. In total, $3$ tents are needed.
In the second test case, three extroverts will take $1$ tent, and $1$ tent will be taken by an introvert. Then, one extrovert and one universal will be left. This extrovert will not be able to live with two others.
Output
组织委员会计划在参观后带奥林匹克竞赛的参与者去远足。目前正在计算需要携带的帐篷数量。已知每个帐篷最多可容纳3人。
参与者中有a个内向者，b个外向者，c个通用型：
- 每个内向者希望独自生活。因此，有内向者的帐篷必须恰好有一个人——只有内向者本人。
- 每个外向者希望与另外两人一起生活。因此，有外向者的帐篷必须恰好有3人。
- 每个通用型对任何选项（独居、与另一人同住或与两人同住）都无所谓。
组织委员会非常尊重每个参与者的意愿，因此他们希望满足所有意愿。
告诉我们在满足所有参与者偏好的情况下，需要携带的最少帐篷数量。如果无法以符合所有愿望的方式容纳参与者，则输出-1。
输入输出数据格式：
输入：
每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。
每个测试用例由一行组成，包含三个整数a、b、c（0≤a，b，c≤10^9）——分别是内向者、外向者和通用型的数量。
输出：
对于每个测试用例，输出一个整数——所需的最少帐篷数量，如果无法容纳参与者，则输出-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
```
输出：
```
3
-1
3
-1
3
28
0
7
8
1666666667
```题目大意： 组织委员会计划在参观后带奥林匹克竞赛的参与者去远足。目前正在计算需要携带的帐篷数量。已知每个帐篷最多可容纳3人。 参与者中有a个内向者，b个外向者，c个通用型： - 每个内向者希望独自生活。因此，有内向者的帐篷必须恰好有一个人——只有内向者本人。 - 每个外向者希望与另外两人一起生活。因此，有外向者的帐篷必须恰好有3人。 - 每个通用型对任何选项（独居、与另一人同住或与两人同住）都无所谓。 组织委员会非常尊重每个参与者的意愿，因此他们希望满足所有意愿。 告诉我们在满足所有参与者偏好的情况下，需要携带的最少帐篷数量。如果无法以符合所有愿望的方式容纳参与者，则输出-1。 输入输出数据格式： 输入： 每个测试包含多个测试用例。第一行包含一个整数t（1≤t≤10^4）——测试用例的数量。接下来是测试用例的描述。 每个测试用例由一行组成，包含三个整数a、b、c（0≤a，b，c≤10^9）——分别是内向者、外向者和通用型的数量。 输出： 对于每个测试用例，输出一个整数——所需的最少帐篷数量，如果无法容纳参与者，则输出-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 ``` 输出： ``` 3 -1 3 -1 3 28 0 7 8 1666666667 ```