34010번 - e-코너 시스템 테스트 (Easy)

문제

도로의 길이에 대한 제한 외에 e-코너 시스템 테스트 (Hard)와의 차이는 없다.

현대모비스의 e-코너 시스템은 자동차의 각 바퀴(휠, Wheel) 안에 구동, 제동, 조향, 서스펜션 시스템을 통합한 차세대 기술로서, e-코너 시스템을 적용한 바퀴는 기존의 자동차 바퀴와 달리 다른 장치와 기계적인 연결 없이 독립적으로 작동한다. 인휠 모터, 전동 브레이크, 전동 조향, 댐퍼 등 4가지의 구성을 하나로 합친 덕분에 바퀴 안쪽에 장착된 인휠 모터는 직접 바퀴를 굴리고 바퀴 옆에 붙은 전동 조향은 직접 방향을 바꿀 수 있으며, 속도를 줄이고 충격을 흡수하는 일은 각각 전동 브레이크와 댐퍼가 맡는다. e-코너 시스템은 이와 같은 시스템으로 바퀴와 구동 부품 사이 그리고 바퀴와 바퀴 사이에 기계적 연결을 없애 그만큼 바퀴를 다양한 각도로 바꾸고 자유자재로 구동력을 전달할 수 있다. 각 바퀴의 각도를 다르게 조절하고 한쪽 바퀴는 전진, 다른 쪽 바퀴는 후진시키는 등의 조작이 가능하여 자동차의 움직임을 아주 다양하게 바꿀 수 있다. e-코너 시스템의 주요 기능은 다음과 같다.

• 크랩 주행: 4개의 바퀴를 직각으로 조향해 평행 이동이 가능한 기술, 게처럼 옆으로 이동하여 평행 주차 가능
• 제로턴: 전륜 내측 조향, 후륜 외측 조향 후 모터를 구동하여 제자리에서 후진 없이 전진 주행으로 방향 전환 가능
• 대각선 주행(사선 주행): 휠의 구동축을 같은 방향으로 조향한 후 원하는 방향으로 이동하여 짧은 구간에서 장애물 회피 가능
• 피봇턴(중심축 회전): 컴퍼스로 원을 그리듯 특정 위치를 중심축 삼아 운전자가 지정한 각도만큼 차량 회전 가능

피봇턴의 동작을 시각적으로 나타내면 다음과 같다.

연구원 유빈이는 e-코너 시스템을 장착한 시험차를 직접 주행하여 그 성능을 테스트하기로 하였다. 시험차 주행은 $N \times N$ 크기의 2차원 격자에서 진행된다.

각 격자에서 상하좌우 인접한 격자로 이동할 수 있는 도로가 있으며 도로를 통하지 않고 이동하는 것은 불가능하다. 가로 방향으로 이동하다가 세로 방향으로 이동하거나, 세로 방향으로 이동하다가 가로 방향으로 이동하는 경우 e-코너 시스템 테스트를 위해 피봇턴을 1회 수행하게 된다.

유빈이의 목표는 출발지인 $(1,1)$에서 도착지인 $(N,N)$까지 최단 경로로 주행하면서 피봇턴을 가능한 한 많이 수행하는 것이다. 유빈이가 주행하게 될 경로를 구해보자.

입력

첫째 줄에 격자의 크기를 나타내는 정수 $N$이 주어진다. $(2 \leq N \leq 502)$

2ドルi$번째 줄에 $N-1$개의 수가 주어지며, $j$번째 수는 $(i,j)$와 $(i,j+1)$를 연결하는 도로의 길이이다. $(i \leq N;,円i,,円j$는 양의 정수$)$

2ドルi+1$번째 줄에 $N$개의 수가 주어지며, $j$번째 수는 $(i,j)$와 $(i+1, j)$를 연결하는 도로의 길이이다. $(i \leq N-1;,円i,,円j$는 양의 정수$)$

모든 도로의 길이는 1ドル$이다.

출력

총 주행 거리와 피봇턴 수행 횟수를 공백으로 구분하여 차례대로 출력한다.

제한

힌트