Задача D. БуКвест ≡

Условие

Юный любитель RPG Вася начал играть в новую компьютерную игру БуКвест. Игровой мир представляет собой прямоугольное поле размером W клеток в ширину и H в высоту. Каждая клетка либо пуста, либо занята стенкой, либо содержит главное сокровище, либо содержит монстра уровня k.

Вася начинает игру в левой верхней клетке (которая всегда пуста), и может свободно перемещаться между пустыми клетками, соседними по горизонтали или вертикали.

Попав в клетку с монстром, Вася вступает с ним в бой. Вася — довольно опытный игрок, и поэтому в конце концов побеждает любого монстра. Однако, на бой с монстром k-го уровня Васе требуется k минут. С другой стороны, в качестве трофея за победу над монстром k-го уровня Вася получает мощное оружие, которое позволяет мгновенно убивать любого монстра уровнем k или ниже, хотя и не помогает сократить время боя против более высокоуровневых монстров.

В первом примере Васе необходимо победить монстра A за одну минуту, затем монстра B за 2 минуты. Во втором примере Вася мог бы победить сначала A, потом B, потом C, затратив 1 + 2 + 3 = 6 минут, но быстрее победить монстра D за 4 минуты, и с полученным за него оружием без дополнительных затрат времени пройти монстров A, B и C.

Помогите Васе найти минимальное количество минут, которое он должен затратить на бои с монстрами, чтобы добраться до главного сокровища.

Отправка решения и тестирование

В качестве решения принимается как программа, так и текстовый файл, содержащий ответ к задаче в требуемом формате (при его отправке следует выбрать в тестирующей системе среду разработки "Answer text").

Баллы будут начисляться пропорционально количеству правильных ответов в выходном файле. Решение будет полностью проверяться сразу после отправки, и участникам будут видны набранные за данную задачу баллы.

Формат входного файла

Первая строка входного файла содержит целое число N — количество тестов в данном файле

Далее N идёт блоков с описанием тестов:

• Первая строка теста содержит два целых числа W H.
• Следующие H строк по W символов содержат описание лабиринта. Пустая клетка обозначаются символом '.' (ASCII 46). Клетка со стенкой — символом '#' (ASCII 44). Клетка с сокровищем — символом '*' (ASCII 42). Клетка с монстром — символом от 'A' (для монстра первого уровня) до 'Z' (для монстра 26-го уровня).
• Каждый тест заканчивается пустой строкой

Формат выходного файла

Выходной файл должен содержать N целых чисел, по одному в строке — ответы на каждый тест.

Ограничения

1 ≤ W, H ≤ 50

Примеры тестов

2
6 5
.####.
...AB.
..###.
...D#*
..###.

6 5
.####.
..ABC.
..###.
...D#*
..###.

3
4