문제
국제 대학생 프로그래밍 경시대회(ACM-ICPC : Association for Computing Machinery-International Collegiate Programming Contest)는 학생 3명과 코치 1명이 1조를 이루어 대회에 참가한다. 팀당 컴퓨터를 한 대만 사용할 수 있으므로 여러 문제를 3명이 어떻게 나누어 푸느냐가 중요하다.
여기 ACM-ICPC 에 참여하게 된 한 팀이 있다. 이 팀의 코치는 필승(?)의 전략을 세웠다. 문제를 받으면 먼저 3명의 선수가 각각 문제를 읽고 각자가 생각하는 난이도를 1(쉬움) ~ 5(어려움) 단계로 표시한다. 그리고 문제의 순서를 변경하지 않고 3부분으로 나누어 3명에게 분배한다. 나눌때는 어느 누구도 1문제 이상을 배정받아야 하고, 2개 이상의 문제를 배정받을 때는 연속된 구간의 문제들을 받는다고 가정한다. 위와같은 기준으로 나눌 때 난이도의 합이 최소가 되게 나누는 것이 이 팀의 전략이다.
이 팀이 문제를 받고 3명의 팀원이 문제별 난이도를 표시한 결과가 주어질 때 최소가 되는 난이도의 합을 구하는 프로그램을 작성하시오.
입력
첫 행에 문제 수 N(3 <= N <= 150,000)이 주어진다.다음 3개의 행에 걸쳐 각 학생이 생각하는 각 문제의 난이도가 행 별로 N개씩 공백으로 구분되어 주어진다. 난이도의 범위는 1이상 5이하의 정수이다.
출력
최소가 되는 난이도의 합을 구하여 하나의 정수로 출력한다.
예제1
입력
3
133
111
123
출력
4
예제2
입력
7
3341344
4251554
5513444
출력
19
힌트
출처
COCI 2014/2015 contest7 3