한번 쏘면 멈출 수 없어

직사각형 게임판에서 Chain Shot! 유형의 게임(SameGame, Jawbreaker, Bubble Shot 등으로도 알려져 있다)을 한다.

게임판의 각 칸에는 색칠된 구슬이 하나씩 놓여 있다. 플레이어는 턴마다 같은 색 구슬이 상하좌우로 인접해 이어진 그룹 하나를 고른다. 고른 그룹의 구슬은 모두 게임판에서 제거된다. 그다음 공중에 뜨게 된 구슬은 모두 바닥으로 떨어지고, 구슬이 하나도 남지 않은 열은 없어지며 양옆의 열이 서로 붙는다.

선택한 그룹	바닥으로 떨어지는 구슬	빈 열 제거	최종 상태

한 턴에 얻는 점수는 고른 그룹에 속한 구슬 개수의 제곱이다. 예를 들어 위 그림에서 크기가 $7$인 그룹을 제거하면 $49$점을 얻는다.

게임판의 구슬이 모두 없어지면 게임이 끝나고, 최종 점수는 각 턴에서 얻은 점수의 합이다.

레벨 설계도는 게임판의 크기와 각 색 구슬의 개수로 이루어진다. 설계도가 주어질 때, 그 설계도로 만들 수 있는 게임판과 각 게임판에서의 플레이 방법을 통틀어 얻을 수 있는 점수의 최댓값을 구하시오.

첫째 줄에 게임판의 행의 수 $h$, 열의 수 $w$, 색상의 수 $c$가 주어진다 ($1 \le h, w \le 10$, $1 \le c \le 9$).

둘째 줄에 $c$개의 양의 정수가 주어지며, $i$번째 정수는 $i$번 색 구슬의 개수이다. 구슬 개수의 합은 $h \cdot w$이다.

설계도로 만들 수 있는 모든 게임판과 각 게임판에서의 모든 플레이 방법을 통틀어 얻을 수 있는 가장 높은 총점을 정수 하나로 출력한다.

구슬 개수가 $4, 4, 7$인 설계도에서는 최대 $81$점을 얻을 수 있다. 아래는 각 색을 한 그룹씩 제거하여 $16 + 16 + 49 = 81$점을 얻는 과정이다.

16점	16점	49점