2인용 페그 게임

Jacquez와 Alia의 부모님은 두 아이를 자주 장거리 여행에 데려간다. 아이들은 이동하는 동안 한 명이 즐기는 삼각형 페그 게임을 하며 시간을 보낸다. 원래 게임에서 플레이어는 한 변에 5개씩, 모두 15개의 구멍이 있는 정삼각형 판을 사용한다. 처음에는 구멍 하나가 비어 있고 나머지 14개에는 페그가 꽂혀 있다. 플레이어는 페그 하나를 들어 다른 페그를 "뛰어넘어" 빈 구멍에 착지한다. 점프는 반드시 직선(가로 또는 대각선) 방향이어야 한다. 뛰어넘긴 페그는 제거된다. 이 게임의 목표는 페그 하나만 남기는 것이다. 그림 J.1은 이 게임에서 점프한 결과를 보여준다.

X                   X
X X                 X O
X X X      -->      X O X
X O X X             X X X X
X X X X X           X X X X X

그림 J.1: 원래 게임에서 가능한 한 가지 이동. 왼쪽은 초기 판으로, X는 페그, O는 빈 구멍을 나타낸다. 이 점프는 위에서 두 번째 줄의 오른쪽 페그를 왼쪽 아래 대각선 방향으로 움직여 세 번째 줄 가운데 페그를 뛰어넘고, 그 페그는 제거된다.

결국 Jacquez와 Alia는 각자 이 게임을 하는 것에 흥미를 잃었다. 두 사람은 함께 할 수 있는 새로운 규칙을 만들기로 한다. 새 규칙에서는 각 페그에 양의 점수 값이 있고, 두 사람이 번갈아 차례를 둔다. 자기 차례에는 점프가 가능하면 반드시 점프해야 한다. 점프의 점수는 점프에 사용된 두 페그 값의 곱이다.

플레이어의 총점은 자신이 한 점프들의 점수 합계다. 점프할 수 있는 이동이 없으면 게임이 끝난다. 각 플레이어의 목표는 게임이 끝났을 때 자신의 총점에서 상대의 총점을 뺀 값을 최대화하는 것이다. 예를 들어 Jacquez는 100 대 60(차이 40)으로 이기는 쪽을, 1 000 대 998(차이 2)로 이기는 쪽보다 선호한다. 마찬가지로 Alia도 Jacquez를 최대한 큰 차이로 이기고 싶어 한다.

이 규칙에서 게임 상태는 위에 나온 각 X를 해당 페그의 값으로 바꾸고, 빈 구멍에는 0을 넣어 표시할 수 있다. 그림 J.2는 한 가지 이동 예를 보여준다.

3                   3
1 6                 1 0
1 7 8      -->      1 0 8
5 0 3 4             5 6 3 4
9 3 2 1 9           9 3 2 1 9

그림 J.2: 새 게임에서 가능한 한 가지 이동으로, 값 6인 페그가 값 7인 페그를 뛰어넘는다. Jacquez가 먼저 두므로 이 이동은 그에게 6 · 7 = 42점이 된다. 값은 첫 번째 예제 입력에서 가져왔다.

Jacquez는 이 게임에서 이기는 데 어려움을 겪고 있다. Jacquez가 먼저 두고 두 플레이어 모두 최적으로 플레이한다고 가정할 때, 그가 얻을 수 있는 최선의 결과를 계산하는 프로그램을 작성하라.

입력은 판의 초기 상태를 나타내는 다섯 줄로 이루어진다. i번째(1 ≤ i ≤ 5) 줄은 i개의 공백으로 구분된 정수를 포함하며, i번째 줄의 페그와 구멍을 나타낸다. 각 정수는 0 이상 100 이하이다. 0은 구멍을, 나머지 값은 페그를 나타낸다. 서로 다른 두 페그가 같은 값을 가질 수도 있다. 15개의 입력 값 중 정확히 하나가 0임이 보장되므로, 모든 입력 판은 구멍이 정확히 하나인 상태로 시작한다.

Jacquez가 먼저 두고 두 플레이어 모두 최적으로 플레이할 때, 게임이 끝난 시점의 Jacquez 점수에서 Alia 점수를 뺀 값을 출력하라.