310961: CF1914D. Three Activities

D. Three Activitiestime limit per test2 secondsmemory limit per test256 megabytesinputstandard inputoutputstandard output

Winter holidays are coming up. They are going to last for $n$ days.

During the holidays, Monocarp wants to try all of these activities exactly once with his friends:

• go skiing;
• watch a movie in a cinema;
• play board games.

Monocarp knows that, on the $i$-th day, exactly $a_i$ friends will join him for skiing, $b_i$ friends will join him for a movie and $c_i$ friends will join him for board games.

Monocarp also knows that he can't try more than one activity in a single day.

Thus, he asks you to help him choose three distinct days $x, y, z$ in such a way that the total number of friends to join him for the activities ($a_x + b_y + c_z$) is maximized.

Input

The first line contains a single integer $t$ ($1 \le t \le 10^4$) — the number of testcases.

The first line of each testcase contains a single integer $n$ ($3 \le n \le 10^5$) — the duration of the winter holidays in days.

The second line contains $n$ integers $a_1, a_2, \dots, a_n$ ($1 \le a_i \le 10^8$) — the number of friends that will join Monocarp for skiing on the $i$-th day.

The third line contains $n$ integers $b_1, b_2, \dots, b_n$ ($1 \le b_i \le 10^8$) — the number of friends that will join Monocarp for a movie on the $i$-th day.

The fourth line contains $n$ integers $c_1, c_2, \dots, c_n$ ($1 \le c_i \le 10^8$) — the number of friends that will join Monocarp for board games on the $i$-th day.

The sum of $n$ over all testcases doesn't exceed $10^5$.

Output

For each testcase, print a single integer — the maximum total number of friends that can join Monocarp for the activities on three distinct days.

ExampleInput

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

Output

30
75
55
56

Note

In the first testcase, Monocarp can choose day $2$ for skiing, day $1$ for a movie and day $3$ for board games. This way, $a_2 = 10$ friends will join him for skiing, $b_1 = 10$ friends will join him for a movie and $c_3 = 10$ friends will join him for board games. The total number of friends is $30$.

In the second testcase, Monocarp can choose day $1$ for skiing, day $4$ for a movie and day $2$ for board games. $30 + 20 + 25 = 75$ friends in total. Note that Monocarp can't choose day $1$ for all activities, because he can't try more than one activity in a single day.

In the third testcase, Monocarp can choose day $2$ for skiing, day $3$ for a movie and day $7$ for board games. $19 + 19 + 17 = 55$ friends in total.

In the fourth testcase, Monocarp can choose day $1$ for skiing, day $4$ for a movie and day $9$ for board games. $17 + 19 + 20 = 56$ friends in total.

题目大意：
寒假即将来临，将持续n天。Monocarp想要尝试以下活动各一次：滑雪、看电影、玩桌游。在第i天，分别有a_i个朋友会和他一起滑雪，b_i个朋友会和他一起看电影，c_i个朋友会和他一起玩桌游。由于Monocarp不能在一天内尝试多个活动，他希望你帮他选择三个不同的日子x、y、z，使得加入他活动的朋友总数(a_x + b_y + c_z)最大化。

输入数据格式：
第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。
每个测试用例的第一行包含一个整数n（3 ≤ n ≤ 10^5）——寒假的天数。
第二行包含n个整数a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^8）——第i天会加入Monocarp滑雪的朋友数量。
第三行包含n个整数b_1, b_2, …, b_n（1 ≤ b_i ≤ 10^8）——第i天会加入Monocarp看电影的朋友数量。
第四行包含n个整数c_1, c_2, …, c_n（1 ≤ c_i ≤ 10^8）——第i天会加入Monocarp玩桌游的朋友数量。
所有测试用例的n之和不超过10^5。

输出数据格式：
对于每个测试用例，输出一个整数——在三个不同的日子中，可以加入Monocarp活动的朋友的最大总数。题目大意： 寒假即将来临，将持续n天。Monocarp想要尝试以下活动各一次：滑雪、看电影、玩桌游。在第i天，分别有a_i个朋友会和他一起滑雪，b_i个朋友会和他一起看电影，c_i个朋友会和他一起玩桌游。由于Monocarp不能在一天内尝试多个活动，他希望你帮他选择三个不同的日子x、y、z，使得加入他活动的朋友总数(a_x + b_y + c_z)最大化。 输入数据格式： 第一行包含一个整数t（1 ≤ t ≤ 10^4）——测试用例的数量。 每个测试用例的第一行包含一个整数n（3 ≤ n ≤ 10^5）——寒假的天数。 第二行包含n个整数a_1, a_2, …, a_n（1 ≤ a_i ≤ 10^8）——第i天会加入Monocarp滑雪的朋友数量。 第三行包含n个整数b_1, b_2, …, b_n（1 ≤ b_i ≤ 10^8）——第i天会加入Monocarp看电影的朋友数量。 第四行包含n个整数c_1, c_2, …, c_n（1 ≤ c_i ≤ 10^8）——第i天会加入Monocarp玩桌游的朋友数量。 所有测试用例的n之和不超过10^5。 输出数据格式： 对于每个测试用例，输出一个整数——在三个不同的日子中，可以加入Monocarp活动的朋友的最大总数。