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

Автор:А. Кленин, А. Жуплев   Ограничение времени:1 сек
Входной файл:input.txt   Ограничение памяти:256 Мб
Выходной файл:output.txt  
Максимальный балл:100  

Условие

Юный любитель 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 идёт блоков с описанием тестов:

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

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

Ограничения

1 ≤ W, H ≤ 50

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

Входной файл (input.txt) Выходной файл (output.txt)
1
2
6 5
.####.
...AB.
..###.
...D#*
..###.

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

3
4

0.074s 0.009s 15