← 返回题目列表

Codeforces · 1792/B

B. 单口喜剧演员

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

Eve 是一位单口喜剧初学者。她的第一场演出总共聚集了两名观众:爱丽丝和鲍勃。

Eve 准备了 $$$a_1 + a_2 + a_3 + a_4$$$ 笑话,按类型分组:

- 类型1:Alice和Bob都喜欢他们;
- 类型 2:Alice 喜欢它们,但 Bob 不喜欢;
- 类型 3:Bob 喜欢它们,但 Alice 不喜欢;
- 类型 4:Alice 和 Bob 都不喜欢他们。

最初,两个观众的情绪都等于 $$$0$$$。当观众听到他/她喜欢的笑话时,他/她的情绪会增加$$$1$$$。当观众听到他/她不喜欢的笑话时,他/她的情绪会下降$$$1$$$。如果观众的情绪变得消极(严格低于零),他/她就会离开。

当有人离开时,伊芙会伤心并结束演出。如果没有人离开,而伊芙也没有笑话了,她也会结束演出。

因此,Eve 希望以一种让节目持续时间尽可能长的方式安排她的笑话。帮助她计算在节目结束之前她最多能讲多少个笑话。

输入

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

每个测试用例的唯一行包含四个整数 $$$a_1, a_2, a_3, a_4$$$ ($$$0 \le a_1, a_2, a_3, a_4 \le 10^8$$$; $$$a_1 + a_2 + a_3 + a_4 \ge 1$$$) — Eve 准备的每种类型的笑话数量。

输出

对于每个测试用例,打印一个整数 - 在至少一名观众离开之前或在讲完笑话之前 Eve 可以讲的最大笑话数。

示例

输入 #1

4
5 0 0 0
0 0 0 5
2 5 10 6
3 0 0 7

输出 #1

5
1
15
7

注意

在第一个测试用例中,Eve 仅具有第一种类型的笑话。因此,没有顺序可供选择。她讲所有的笑话,爱丽丝和鲍勃都喜欢。他们的心情变得$$$5$$$。夏娃讲完笑话后节目就结束了。

在第二个测试用例中,Eve 仅具有第四种类型的笑话。于是,再次没有顺序可供选择。她讲了一个笑话,爱丽丝和鲍勃都不喜欢它。他们的情绪下降了 1,变成 $$$-1$$$。两人心情都很消极,于是双双离开,演出结束。

在第三个测试用例中,首先,Eve 讲了第一种类型的两个笑话。 Alice 和 Bob 的心情都是 $$$2$$$。然后她就可以讲第三种类型的$$$2$$$笑话。爱丽丝的心情变成$$$0$$$。鲍勃的心情变得 $$$4$$$。然后是第二类$$$4$$$笑话。爱丽丝的心情变成$$$4$$$。鲍勃的心情变得$$$0$$$。然后是第三种类型的另一个 $$$4$$$ 笑话。爱丽丝的心情变成$$$0$$$。鲍勃的心情变得 $$$4$$$。然后剩下第二类笑话。爱丽丝的心情变成$$$1$$$。鲍勃的心情变成$$$3$$$。然后再讲一个第三类笑话,再讲一个第四类笑话。 Alice 的情绪变为 $$$-1$$$,她离开,演出结束。

在第四个测试用例中,Eve 应该首先讲两个观众都喜欢的笑话,然后讲他们不喜欢的笑话。她可以讲第四种类型的$$$4$$$笑话,直到观众离开。