문제

PebbleSum 문제를 최대값뿐만 아니라 최적 경로(최적 패턴 열)를 출력하도록 확장한다.

• PebbleSum 문제 바로가기: https://litmus.jedutools.io/problem/10738

패턴 번호는 다음과 같다.

• 패턴 1: 위
• 패턴 2: 가운데
• 패턴 3: 아래
• 패턴 4: 위와 아래

입력

• 첫 줄에는 보드판의 가로 크기 m이 들어온다.
• 그 다음 3줄에는 각 행의 원소값이 들어온다.

출력

• 규칙에 맞게 조약돌을 놓고 그 합의 모든 경우의 수 중 가장 큰 값을 출력한다.
• 그다음 줄에는 가장 큰 값에 해당하는 최적 패턴 열을 출력한다.

제한

• 1 ≤ m ≤ 100
• 각 원소값은 -1,000 이상 1,000 이하의 정수이다.
• 최적 패턴 열이 하나뿐인 입력만 주어진다.

예제 입력 1

8
6 7 12 -5 5 3 11 3
-8 10 14 9 7 13 8 5
11 12 7 4 8 -2 9 4

예제 출력 1

106
4 2 4 2 4 2 4 2