A supercomputer has several processors to deploy for execution. They are arranged sequentially in a row from 1 to n. The efficiency of each processor depends upon the order of deployment of its adjacent processors. For the ith processor, the efficiency of the th processor is no adjacent[in], one adjacent[i], or both adjacent[i] when neither, one, or both adjacent processors is deployed before processor i. Note: The 1st and nth processors can only have one adjacent. Find the maximum possible sum of efficiencies amongst all possible orders of deployment.

Example

There are n = 4 processors.

no_adjacent = [1, 2, 3, 4]

one_adjacent = [4, 4, 2, 1]

both_adjacent = [0, 1, 1, 0]

Consider the following orders of deployment (1- based indexing):

The deployment sequence is (1→3→4→2).

Then, the sum of efficiencies = no_adjacent[1] +

no_adjacent[3] + one_adjacent[4] + both_adjacent[2]=1+3+1+1=6.

Let the deployment sequence be (4→2→1→3),

no adjacent[4] + no adjacent[2] + one adjacent[1] + both_adjacent[3]=4+2+4+1=11.

Let the deployment sequence be (4-3-2-1),

no_adjacent[4] + one_adjacent[3] + one_adjacent[2] + one_adjacent[1] = 4+2+4+4=14.

.

Similarly, other deployment orders can be performed.

Amongst all possible deployments, the maximum possible sum of efficiencies is 14.

**Constraints **

2 ≤ n ≤ 10^5

1 ≤ no_adjacent[i], one_adjacent[i],

both adjacent[i] ≤ 10^9

I was trying to solve this question Can anyone help me? (published)