두부 장수 장홍준
시간 제한2초메모리 제한128 MB
글자 등급이 적힌 격자를 겹치지 않는 2x1 도미노로 덮어 등급 조합 가격의 합을 최대화하는 문제이며, 덮이지 않은 칸은 가치가 0입니다.
문제
장홍준은 세로 N, 가로 M 크기의 두부판을 2 x 1 크기의 조각으로 잘라 판다. 각 칸에는 A, B, C, D, F 중 하나의 등급이 적혀 있으며, 두 칸을 붙여 만든 한 조각의 가격은 두 등급의 조합으로 정해진다.
가격표는 다음과 같다.
두 등급의 순서는 가격에 영향을 주지 않는다. 두부판에서 겹치지 않는 2 x 1 조각을 가로 또는 세로로 잘라낼 수 있고, 조각에 포함되지 않는 한 칸짜리 두부는 가격이 0이므로 버린다. 전체 가격 합의 최댓값을 구하시오.
입력
첫째 줄에 두부판의 세로 크기 N과 가로 크기 M이 주어진다. N과 M은 1 이상 14 이하의 정수이다.
다음 N개의 줄에는 각 줄마다 M개의 문자가 주어진다. 각 문자는 해당 칸의 등급을 나타내며 A, B, C, D, F 중 하나이다.
출력
잘라낸 두부 조각들의 가격 합으로 만들 수 있는 최댓값을 출력한다.