19573번 - 꿀벌

작은 벌집에 살고 있는 꿀벌이 있다. 오늘은 벌집 여기저기를 돌아다니면서 벌집에 저장되어 있는 꿀을 배불리 먹으려 한다.

벌집의 각 칸에는 꿀이 저장되어 있는데, 꿀을 먹어서 얻거나 잃는 에너지는 칸마다 다르다. 꿀벌은 아무 칸에서나 시작해서 다음과 같이 움직이면서 방문하는 모든 칸에 있는 꿀을 전부 먹고 아무 칸에서나 나올 것이다. 한 칸도 방문하지 않는 것도 가능하다.

• 인접한 칸으로 이동한다. 이동하는 데에는 에너지가 소모되지 않는다.
• 벌집 안의 다른 임의의 칸으로 날아간다. 벌의 눈은 육각형 모양이기 때문에, 항상 벌집의 벽과 수직인 6개 방향 중 하나로 날아다닌다. 날아다니는 동안 방향을 바꿀 수 있다. 날아가는 데에는 (벌집 거리 − 1) × F만큼의 에너지가 소모된다.
  • 어느 두 칸의 벌집 거리는, 인접한 칸의 거리를 1이라고 정의하고, 어떤 한 칸에서 다른 한 칸으로 인접한 칸들만 거쳐서 이동했을 때의 두 칸의 최단 경로의 거리로 정의한다.
• 벌은 날아다니면서 페로몬을 뿌린다. 페로몬은 피로를 없애 주기 때문에, 방향과 상관없이 날아왔던 경로를 다시 지나는 경우에는 에너지가 소모되지 않는다. 또한 페로몬은 금방 사라지지 않아서 나중에 다시 같은 경로를 지나더라도 에너지를 소모하지 않는다.

벌집의 크기 N과, 모든 칸에 대해 각 칸의 꿀을 먹었을 때 얻거나 잃는 에너지의 정보가 주어질 때, 꿀벌이 얻을 수 있는 최대 에너지를 계산하자. 벌집의 크기가 N이라는 것은 벌집의 가운데 칸에서 벌집 거리로 가장 멀리 갈 수 있는 칸까지의 벌집 거리가 N이라는 뜻이다.

첫째 줄에는 벌집의 크기 N과 문제에서 언급한 상수 F가 주어진다. (1 ≤ N ≤ 6, 1 ≤ F ≤ 10⁹)

두 번째 줄부터 (2N − 1)개 줄에는 각 칸마다 벌집에 저장되어 있는 꿀을 먹어서 얻을 수 있는 에너지의 정도가 위에서 아래, 왼쪽에서 오른쪽 순서대로 주어진다. 에너지는 절댓값이 10⁹보다 크지 않은 정수이다.

꿀벌이 얻을 수 있는 최대 에너지를 출력한다.