크기의 직사각형 피자가 크기의 정사각형 조각 개로 나뉘어 있다. 하지만 모든 경계가 잘린 것은 아니다. 잘리지 않은 경계를 공유하는 두 조각은 아직 서로 붙어 있다.
조각 하나를 먹으면 그 조각과 그 조각에 닿은 잘리지 않은 경계가 모두 사라진다. 잼민이는 현재 남은 조각 중 잘리지 않은 경계로 붙어 있는 이웃이 개 이하인 조각만 먹을 수 있다. 아빠는 남아 있는 어떤 조각이든 먹을 수 있다.
잼민이가 첫 조각을 먹은 뒤에는, 자신이 바로 전에 먹은 조각과 처음부터 잘리지 않은 경계를 공유한 조각만 다음으로 먹을 수 있다. 아빠는 잼민이가 첫 조각을 먹기 전이나 먹는 도중에도 자유롭게 조각을 먹을 수 있으며, 같은 사람이 여러 조각을 연속해서 먹어도 된다.
처음에는 모든 피자 조각이 하나로 연결되어 있으며, 잘리지 않은 경계의 수는 총 개이다. 두 사람이 협력할 때 잼민이가 먹을 수 있는 조각 수의 최댓값을 구해 보자.
첫째 줄에 , 이 공백으로 구분되어 주어진다.
둘째 줄부터 개의 줄에 걸쳐 개의 정수 가 공백으로 구분되어 주어진다.
잼민이가 먹을 수 있는 조각 수의 최댓값을 출력한다.
위에서 번째 줄, 왼쪽에서 번째 조각을 라 하자.
첫 번째 예제에서 피자 조각 개는 , , , , , 순서로 고리 모양으로 붙어 있다. 처음에는 모든 조각이 붙어 있는 이웃이 개이므로 잼민이는 아무 조각도 먹을 수 없고, 아빠가 먼저 한 조각을 먹어야 한다.
의 값은 행 열의 조각이 오른쪽 조각 및 아래쪽 조각과 붙어 있는지를 나타낸다. 각 값의 의미는 다음과 같다.
격자 밖의 조각과 붙어 있는 경우는 주어지지 않는다.
, 이다. 모든 피자 조각은 하나로 연결되어 있고, 잘리지 않은 경계의 수는 정확히 개이다.
입력으로 주어지는 모든 수는 정수이다.
예를 들어 아빠가 를 먹으면, 잼민이는 , , , , 을 차례대로 먹을 수 있다. 잼민이가 각 조각을 먹을 때 그 조각에 붙어 있는 남은 이웃은 개 이하이고, 연속해서 먹은 두 조각은 처음부터 붙어 있던 조각이다. 아빠가 적어도 한 조각은 먹어야 하므로 잼민이가 먹을 수 있는 조각 수의 최댓값은 이다.
두 번째 예제에서는 가장자리의 조각 개가 고리 모양으로 붙어 있고, 가운데 조각 는 에만 붙어 있다. 아빠가 을 먹으면 잼민이는 , , , , , , , 을 차례대로 먹어 조각을 먹을 수 있다.