Background

Team members Stjepan, Ivan, and Gustav from the University of Zagreb are in Morocco attending the ACM International Collegiate Programming Contest World Finals. Their coach Goran has come up with an unbeatable strategy for solving the problems in the finals.

Problem Description

At the beginning, each team member quickly estimates the difficulty of each of the $n$ problems. These difficulties are described by numbers from $1$ to $5$; the larger the number, the harder the problem.

After that, they will divide the work among themselves. For simplicity, the set of problems will be split into three parts, so that each team member gets a non-empty consecutive segment of problems to think about. The division is made to minimize the sum of estimated difficulties, counting only the estimated difficulty values given by the team member who is assigned that segment. Your task is to compute this minimum possible total sum.

Input Format

The input consists of four lines.

The first line contains an integer $n$, the number of problems.
Lines 2 to 4: on line $i+1$ there are $n$ integers $d_{i,1}, d_{i,2}, \dots, d_{i,n}$, where $d_{i,j}$ is member $i$'s estimated difficulty for problem $j$.

Output Format

Output a single line containing one integer, the minimum possible total estimated difficulty sum.

3
1 3 3
1 1 1
1 2 3

4

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

19

Hint

[Sample 1 Explanation]

Assign problem $1$ to member $1$, assign problem $3$ to member $2$, and assign problem $2$ to member $3$. Then the total difficulty sum is $1+1+2=4$. It can be proven that no assignment has a smaller total difficulty sum.

[Constraints]

For all testdata, $3\leqslant n\leqslant 1.5\times 10^5$, $1\leqslant d_{i,j}\leqslant 5$.

[Source]

This problem is from COCI 2014-2015 CONTEST 7 T3 ACM, and follows the original testdata configuration, with a full score of $100$ points.

Translated and整理 (zhengli) provided by Eason_AC.

Translated by ChatGPT 5