P7793 [COCI 2014/2015 #7] ACM

Zagreb 大学的团队的成员 Stjepan、Ivan 和 Gustav 正在摩洛哥参加 ACM 国际大学生程序设计竞赛的世界决赛。他们的技术指导 Goran 想出了一个无敌的策略，用于解决决赛中的题目。

在一开始，每个团队成员迅速估计 $n$ 道题目中每题的难度。这些难度用 $1$ 到 $5$ 的数字描述，数字越大，难度也就越大。 在这之后，他们之间将分配任务。为了简单起见，任务阵列将被分成三部分，以便每个团队成员得到一个**非空**的连续任务序列来思考。这种分配是为了使估计的难度之和最小，而只计算被分配到该任务的团队成员的估计难度值。你的任务是计算这个最小的可能总和。

输入共四行。 第一行输入一个整数 $n$，表示问题的数量。 第二到第四行，第 $i+1$ 行 $n$ 个整数 $d_{i,1},d_{i,2},\dots,d_{i,n}$，表示第 $i$ 号成员对于这 $n$ 道题目估计的难度。

输出仅一行，一个整数，表示最小可能的估计难度总和。

**【样例 1 解释】** 给第 $1$ 号成员分配第 $1$ 题，给第 $2$ 号成员分配第 $3$ 道题，给第 $3$ 号成员分配第 $2$ 道题。这样分配的难度总和为 $1+1+2=4$。可以证明没有难度总和更小的分配方案。 **【数据范围】** 对于所有数据，$3\leqslant n\leqslant 1.5\times 10^5$，$1\leqslant d_{i,j}\leqslant 5$。 **【题目来源】** 本题来源自 **_[COCI 2014-2015](https://hsin.hr/coci/archive/2014_2015/) [CONTEST 7](https://hsin.hr/coci/archive/2014_2015/contest7_tasks.pdf) T3 ACM_**，按照原题数据配置，满分 $100$ 分。 由 [Eason_AC](https://www.luogu.com.cn/user/112917) 翻译整理提供。