25241번 - 가희와 사직 구장

가희가 응원하고 있는 롯데 자이언츠의 홈 구장인 사직 구장의 무대는 R행 C열로 이루어져 있습니다. 가희는 이 무대에 N명의 아이돌을 배치하려고 합니다. N명의 아이돌은 각각 1번부터 N번까지의 번호를 가집니다.

이 중 3명은 삼총사라고 불립니다. 이들은, 서로가 상하좌우나 대각선 방향으로 인접해 있을 때 고유의 효과를 냅니다.

가희는 사직 구장의 무대에 N명의 아이돌을 적절히 배치해서, 그들의 매력을 최대치로 하고 싶습니다. 어떻게 하면 좋을지 알려주세요.

첫 번째 줄에 R과 C와 N이 공백으로 구분되어 주어집니다.

두 번째 줄에 삼총사의 번호 a₁, a₂, a₃이 공백으로 구분되어 주어집니다.

세 번째 줄에 번호가 a₁인 아이돌과 번호가 a₂인 아이돌이 인접해 있을 때, 번호가 a₂인 아이돌과 번호가 a₃인 아이돌이 인접해 있을 때, 번호가 a₁인 아이돌과 번호가 a₃인 아이돌이 인접해 있을 때 추가로 올라가는 매력도가 공백으로 구분되어 주어집니다.

다음 R개의 줄에는 C개의 수가 공백으로 구분되어 주어집니다. r번째 줄의 c번째 수는 r행 c열에 아이돌이 있을 때 올라가는 매력을 의미합니다.

가희가 N명의 아이돌을 무대에 올렸을 때, 얻을 수 있는 매력의 최댓값을 출력해 주세요.

• 1 ≤ R ≤ 200
• 1 ≤ C ≤ 200
• 3 ≤ R × C​ ≤ 200
• 3 ≤ N ≤ R × C
• 1 ≤ 무대의 각 지점에 서 있을 때 올라가는 매력 ≤ 10⁴
• a₁, a₂, a₃은 모두 다르며, 1 이상 N 이하의 정수입니다.
• a₁과 a₂가 인접해 있을 때, a₂과 a₃이 인접해 있을 때, a₁과 a₃이 인접해 있을 때 추가로 올라가는 매력도는 1 이상 10⁴ 이하의 정수입니다.