eolymp
bolt
Попробуйте наш новый интерфейс для отправки задач

Сон

Лимит времени 1 секунда
Лимит использования памяти 64 MiB

Любознательный школьник Петя очень любит программировать. Однажды он настолько увлекся этим делом, что уснул прямо за компьютером! Пете приснилось, что он попал в альтернативную реальность. Альтернативная реальность представляет собой прямоугольный лабиринт, который можно изобразить в виде таблицы размером r×c клеток. Чтобы не опоздать школу, Пете нужно найти выход из лабиринта. Начальная позиция Пети обозначается символом 'S', выход из альтернативной реальности – 'E'. За один ход Петя перемещается в одну из четырех смежных клеток (влево, вправо, вниз, вверх). Если клетка занята стеной (символ 'X'), то Петя пройти в нее не может. В некоторых клетках расположены двери с замками одного из четырех цветов ('R', 'G', 'B', 'Y'). Для прохода в эту клетку, необходимо обладать ключом определенного цвета. Так как ключи многоразовые, то одним ключом можно открыть сколь угодно много соответствующих ему замков.

Властелин альтернативной реальности предлагает Пете купить ключи, чтобы пройти к выходу. У нашего героя совсем немного денег с собой, поэтому ему хочется потратить как можно меньше денег и при этом пройти к выходу. Помогите ему определить минимальную сумму денег, которую нужно потратить на ключи.

Входные данные

Первая строка содержит количество тестов. Каждый тест начинается с двух целых чисел r и c (1 r, c50). Вторая строка теста содержит 4 целых числа p_i, стоимости покупки ключей 'R', 'G', 'B' и 'Y' соответственно (p_i100). Далее следуют r строк, в каждой из которых c символов, описывающих лабиринт. Каждый лабиринт содержит только один символ 'S' и один символ 'E'.

Выходные данные

Для каждого теста в отдельной строке выведите минимальную сумму денег, необходимую для покупки набора ключей, позволяющего пройти к выходу. Если пути к выходу из альтернативной реальности не существует, и Петя обречен проспать уроки, выведите "Sleep".

Пример

Входные данные #1
2
3 7
1 1 1 1
XXXXXXX
XS.X.EX
XXXXXXX
6 6
1 5 3 1
XXXXXX
XS.X.X
X..R.X
X.XXBX
X.G.EX
XXXXXX
Выходные данные #1
Sleep
4