Maximum sum in 3-array

Maximum sum in 3-array

সময় লিমিট: 2.0 s

মেমরি লিমিট: 512.0 MB

Description

Life is sorted when you find true happiness. True happiness exist when you find out a supportive partner. Nayem is searching for a partner, but still he can not manage single one. Roy stick up for him, told that if he solve this problem then ready for assist him a partner.

The Problem is very simple,

You are given 3 array A[], B[], C[] of equal length \(N\)

You need to construct an Array D[] in following way,

  • Array D[] has exaclty N elements.

  • All selective elements comes from A[], B[] or C[].

  • You can select only one of \(Ai,Bi,Ci\)-th element for all i from 1 to \(N\). in other words if you select the 2nd element from array A[] then you cannot take the 2nd elements of array B[] and C[] and vice versa.

  • you can not select same index twice from any array and two consecutive elements from any array.

  • Total sum of array D[] is as maximum as possible.

Unfortunately, Nayem is busy with his job, so he need your help to solve this problem.

Input

First line takes an integer \(T\) : number of testcases
in each of the testcase :
first line takes an integer \(N\) : size of the array D[]
second line takes \(N\) integers : elements of array A[]
third line takes \(N\) integers : elements of array B[]
fourth line takes \(N\) integers : elements of array C[]

\(1 <= T <= 100\)
\(1 <= N <= 10^5\)
\(-10^4 <= Ai,Bi,Ci <= 10^4\)

Output

Output 1 integer in each of T lines : The maximum possible sum of the array D[]

Sample

Input Output
1
4
6 6 -1 1
-1 4 0 -1
-2 1 3 -5
14

In the first test case,

we can construct D[] by the following way,

1st index from A[]. D={6}.

second index from B[]. D={6,4}. note we can not select two consecutive elements from any array.

3rd index from C [], D={6,4, 3}.

4 th index from A [], D={6,4,3,1}.

so total sum of D is 14 which is maximum.

Information

ID
1046
Difficulty
8
Category
(None)
Tags
(None)
# Submissions
52
Accepted
8
Accepted Ratio
15%
Uploaded By

Related

In following contests:

TLE_Headquarters - round #1