Three Activities
Contest: Codeforces Round 916 (Div. 3)
Difficulty rating: 1200
Tags: brute force, dp, greedy, implementation, sortings

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 format:
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 format:
For each testcase, print a single integer — the maximum total number of friends that can join Monocarp for the activities on three distinct days.

Constraints:
Time limit: 2.0 s
Memory limit: 256.0 MB

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.

Example input:
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

Example output:
30
75
55
56

Editorial:
The main idea of the problem is that almost always you can take the maximum in each array. And when you can't, you don't need to look at a lot of smaller numbers. In particular, it is enough to consider the three largest numbers from each array.
Let's show the correctness of this for the first array. There always exists an optimal answer in which one of the three largest numbers is taken from array $$$a$$$. Let's fix some taken elements in arrays $$$b$$$ and $$$c$$$. Then at least one of the three positions of the largest elements in $$$a$$$ is different from both fixed position.
The argument is generalized to all three arrays similarly.
Thus, the solution looks as follows. Find the positions of the three maximums in each array and iterate over the answer in $$$3^3$$$. Finding three maximums can be done using sorting or in one linear time pass over the array.