ACM

Interview

Time limit1sMemory limit64 MB

Summary

Split the task list into three nonempty consecutive blocks and assign one member to each block to minimize the summed difficulty estimates.

Level: Medium4 of 10
Topics: Prefix sum, Brute force
Solved: No attempts yet

Problem

The University of Zagreb team, Stjepan, Ivan and Gustav, is competing in the World Finals of the ACM International Collegiate Programming Contest in Morocco. Goran, their technical guide, has prepared a winning strategy for solving the tasks in the finals.

At the very start, each team member quickly estimates the difficulty of all $N$ tasks. A difficulty is a number from 1 to 5 with the following meaning.

1: hehehe
2: bring it on!
3: well OK.
4: hmmmm. . .
5: are you insane?

After that they share out the tasks. To keep things simple, the list of tasks is cut into three parts and each team member takes one block of consecutive tasks. No block may be empty. They are free to decide who takes which block. The sum of difficulties adds, for every task, only the estimate written by the member that task went to, and they cut the list so that this sum is as small as possible. Compute the smallest possible sum.

Input

The first line contains the integer $N$ ( $3 \le N \le 150\,000$ ), the number of tasks.

Each of the next three lines contains $N$ integers between 1 and 5. The first of those lines holds Stjepan's estimates, the second Ivan's and the third Gustav's.

Output

Print the minimal sum of difficulties on a single line.

Hint

In the first sample Stjepan takes the first task, Gustav the second and Ivan the third.

Examples2

Example 1
Input
```
3
1 3 3
1 1 1
1 2 3
```
Expected output
```
4
```

Example 2

Input

7
3 3 4 1 3 4 4
4 2 5 1 5 5 4
5 5 1 3 4 4 4

Expected output