학과 리셉션

학위를 받고 (그리고 술 장식의 위치를 옮긴 뒤) 드디어 학과 리셉션에 갈 시간입니다. 정확히는 습격이 아니라 방문이지만요. 아쉽게도 시간이 넉넉하지 않습니다. 가족, 친구들과 사진 촬영 약속이 있기 때문입니다. 그래서 주어진 시간 안에 맛있는 음식을 최대한 많이 먹는 것이 목표입니다. 핵심은 '맛있는'입니다. 학과마다 음식의 질이 크게 다르므로, 어느 리셉션에 갈지 신중하게 골라야 합니다.4

주의할 점이 세 가지 있습니다. (1) 일부 리셉션은 출입을 통제합니다. 해당 학과 학생이거나 직원과 친구 사이처럼 어떤 권한이 없으면 들어갈 수 없습니다. (2) 사람이 많이 몰리는 곳이 있어서 그곳에서는 이동이 느려집니다. (3) 충분히 먹지 않으면 맛있는 음식에 도달하기 전에 배고픔으로 쓰러질 수 있습니다. 먹을 수 있는 음식 점수의 합을 최대로 구하는 프로그램을 작성하세요.

캠퍼스는 직사각형 지도로 표현됩니다. 한 걸음에 상하좌우로 인접한 칸 한 개씩 이동할 수 있습니다(대각선 이동은 불가능). 한 걸음을 걸을 때마다 에너지가 1 단위 줄고, 음식을 1 단위 먹을 때마다 에너지가 1 단위 회복됩니다. 음식 1 단위를 먹으려면 음식 칸에 1 단위 시간 머물러야 합니다. 출발 칸과 도착 칸('S'와 'T'로 지도에 표시됨) 외에 지도에는 다음 종류의 칸이 있습니다.

• 이동 칸. '.', ':', ';', '#'로 표시합니다. 음식도 출입 통제도 없습니다. 이 칸에 들어가면 시간이 걸립니다. '.'는 1 단위, ':'는 2 단위, ';'는 3 단위, '#'는 4 단위입니다. '.'는 빈 통로이고, '#'는 트로이 용사 동상이나 초콜릿 분수 주변처럼 사람이 아주 많이 몰리는 곳이라고 생각하면 됩니다.
• 출입 통제 칸. 대문자 A부터 H까지로 표시합니다. 학과가 이곳에 검문소를 세워 음식에 욕심 많은 학생들을 막고 있습니다. 해당 권한이 있을 때만 들어갈 수 있습니다. 보유한 권한 목록은 입력으로 주어집니다. 출입 통제 칸에 들어가면 1 단위 시간이 걸립니다. 출발 칸이나 도착 칸에 들어갈 때도 1 단위 시간이 걸립니다.
• 음식 칸. 숫자 1부터 5까지로 표시합니다. 음식 칸에 들어가면 1 단위 시간이 걸립니다. 그 뒤 기다릴 때마다(즉 움직이지 않을 때마다) 에너지가 1 단위 늘고, 해당 숫자만큼의 음식 점수를 얻습니다.

목표는 'S'에서 출발해 주어진 시간 이하에 'T'에 도착하는 것입니다. 이때 에너지가 0 이하로 떨어지면 안 되며, 'T'에 도착하는 마지막 걸음도 포함합니다. 그 과정에서 얻는 음식 점수의 합을 최대화하세요.

4 EE는 왜 항상 CS보다 음식이 훨씬 맛있을까요?

첫 줄에는 데이터 세트의 개수 K(1 이상 100 이하)가 주어집니다. 각 데이터 세트는 다음 형식입니다.

데이터 세트의 첫 줄에는 정수 h, w, e, t가 차례로 주어지고, 이어서 A부터 H까지의 대문자로 이루어진 문자열이 주어집니다. h와 w는 1 이상 30 이하, e와 t는 1 이상 100 이하입니다. h와 w는 지도의 세로와 가로 길이, e는 초기 에너지, t는 가족과 친구를 만나기까지 남은 시간 단계 수입니다. 문자열은 최대 8자이며 중복되지 않고, 비어 있을 수도 있습니다. 이 문자열은 보유한 출입 권한을 나타냅니다.

다음 h줄에는 각각 정확히 w개의 문자가 주어집니다. 각 문자는 위에서 설명한 기호 중 하나입니다. 즉 A부터 H까지의 문자, 'S', 'T', 1부터 5까지의 숫자, '.', ':', ';', '#' 중 하나입니다. 지도에는 'S'가 정확히 하나, 'T'가 정확히 하나 있습니다.

각 데이터 세트마다 "Data Set x:"를 한 줄에 출력합니다. x는 데이터 세트 번호입니다. 다음 줄에는 시간 t 이하에 만남 장소에 도착하면서 얻을 수 있는 음식 점수의 최대 합을 출력합니다. 시간 t 이하에 도착할 수 없다면 "Impossible"을 출력합니다.

각 데이터 세트 뒤에는 빈 줄을 출력합니다.

처음에는 매우 배고픕니다(에너지: 4). 그래서 초기 에너지로는 왼쪽 위 모서리의 품질이 낮은 음식까지만 갈 수 있습니다. 다른 곳에 가려면 충분히 먹어야 합니다. 'B' 출입 통제와 오른쪽 위의 매우 느린 칸 때문에 시간 37의 만남에 맞춰 품질 4와 5의 음식이 있는 곳에 도착할 수 없습니다. 그래서 왼쪽 아래쪽에 있는 품질 3 음식까지 갈 수 있을 만큼만 먹습니다. 곧장 아래로 가면 느리기 때문에 오른쪽으로 한 칸 이동하면서 'D', 'A', 'E' 권한을 사용합니다. 품질 3 음식은 만남 장소에 안전하게 도착할 수 있을 만큼 먹고, 그 뒤 출발해 제시간에 도착합니다. 품질 3 음식에 도달할 만큼의 에너지를 얻기 위해 품질이 낮은 음식을 7 단위 시간 먹고, 품질 3 음식을 11 단위 시간 먹었으므로, 합계는 $7 + 3 \times 11 = 40$ 음식 점수입니다.

처음에 왼쪽 위 모서리로 가는 대신 위쪽 가운데의 품질 1 음식으로 갈 수도 있었습니다. 하지만 그곳에서 먹더라도 'B' 출입 통제와 오른쪽 위의 느린 칸 때문에 품질 4나 5 음식을 충분히 먹을 수 없어 더 나은 결과가 나오지 않습니다. 도달할 수 있는 품질 2 음식으로 가면 얻는 점수도 적습니다.