寒假即将来临。它们将持续 $$$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$$$ 好友。