← 返回题目列表

Codeforces · 1914/D

D. 三项活动

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

寒假即将来临。它们将持续 $$$n$$$ 天。

在假期期间,Monocarp 想和他的朋友们一起尝试所有这些活动一次:

- 去滑雪;
- 在电影院看电影;
- 玩棋盘游戏。

Monocarp 知道,在第 $$$i$$$ 天,恰好有 $$$a_i$$$ 朋友会和他一起滑雪,$$$b_i$$$ 朋友会和他一起看电影,$$$c_i$$$ 朋友会和他一起玩棋盘游戏。

Monocarp 也知道他不能在一天内尝试超过一项活动。

因此,他要求你帮助他选择三个不同的日子 $$$x, y, z$$$,以使参加他活动的朋友总数 ($$$a_x + b_y + c_z$$$) 最大化。

输入

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

每个测试用例的第一行包含一个整数 $$$n$$$ ($$$3 \le n \le 10^5$$$) — 冬季假期的持续时间(以天为单位)。

第二行包含 $$$n$$$ 整数 $$$a_1, a_2, \dots, a_n$$$ ($$$1 \le a_i \le 10^8$$$) - 第 $$$i$$$ 天将加入 Monocarp 滑雪的好友数量。

第三行包含 $$$n$$$ 整数 $$$b_1, b_2, \dots, b_n$$$ ($$$1 \le b_i \le 10^8$$$) — 在第 $$$i$$$ 天加入 Monocarp 看电影的好友数量。

第四行包含 $$$n$$$ 整数 $$$c_1, c_2, \dots, c_n$$$ ($$$1 \le c_i \le 10^8$$$) - 第 $$$i$$$ 天加入 Monocarp 玩棋盘游戏的好友数量。

所有测试用例的 $$$n$$$ 总和不超过 $$$10^5$$$。

输出

对于每个测试用例,打印一个整数 - 可以加入 Monocarp 参加三天不同活动的最大好友总数。

示例

输入 #1

4
3
1 10 1
10 1 1
1 1 10
4
30 20 10 1
30 5 15 20
30 25 10 10
10
5 19 12 3 18 18 6 17 10 13
15 17 19 11 16 3 11 17 17 17
1 17 18 10 15 8 17 3 13 12
10
17 5 4 18 12 4 11 2 16 16
8 4 14 19 3 12 6 7 5 16
3 4 8 11 10 8 10 2 20 3

输出 #1

30
75
55
56

注意

在第一个测试用例中,Monocarp 可以选择 $$$2$$$ 滑雪日、$$$1$$$ 电影日和 $$$3$$$ 棋盘游戏日。这样,$$$a_2 = 10$$$ 朋友将与他一起滑雪,$$$b_1 = 10$$$ 朋友将与他一起看电影,$$$c_3 = 10$$$ 朋友将与他一起玩棋盘游戏。好友总数为 $$$30$$$。

在第二个测试用例中,Monocarp 可以选择 $$$1$$$ 滑雪日、$$$4$$$ 电影日和 $$$2$$$ 棋盘游戏日。 $$$30 + 20 + 25 = 总共 75$$$ 好友。请注意,Monocarp 无法为所有活动选择 $$$1$$$ 日期,因为他无法在一天内尝试多个活动。

在第三个测试用例中,Monocarp 可以选择 $$$2$$$ 滑雪日、$$$3$$$ 电影日和 $$$7$$$ 棋盘游戏日。 $$$19 + 19 + 17 = 总共 55$$$ 好友。

在第四个测试用例中,Monocarp 可以选择 $$$1$$$ 滑雪日、$$$4$$$ 电影日和 $$$9$$$ 棋盘游戏日。 $$$17 + 19 + 20 = 总共 56$$$ 好友。