Учебная тревога

Джоко участвует в пожарных учениях, организованных пожарной службой Джакарты для отбора новых пожарных. В рамках учений необходимо спасти добровольцев, изображающих потерявших сознание людей, которые оказались в ловушке в здании за ограниченное время. Здание состоит из нескольких этажей, и добровольцы распределены по всему зданию. Каждому добровольцу присвоены определенные баллы. Кандидат должен спасти добровольцев, перенеся их к выходу, и за каждого спасенного добровольца он получит соответствующие баллы.

Каждый этаж здания можно представить в виде сетки ячеек. Каждая ячейка может быть препятствием, пустым пространством, лестницей или входом/выходом.

Кандидат начинает с точки входа, которая находится в единственной ячейке на первом этаже здания. Он может перемещаться в любую соседнюю ячейку без препятствий (на север, юг, запад или восток) или подниматься вверх или вниз по лестнице за 1 секунду. Когда кандидат несет добровольца, его движение замедляется до 2 секунд на ячейку. Если кандидат находит добровольца, он может решить спасти его или нет, но если решает спасти, то должен нести его обратно к выходу без остановки. Одновременно он может нести только одного добровольца.

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

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

Первая строка входных данных содержит целое число T (T ≤ 100), обозначающее количество случаев. Каждый случай содержит пять целых чисел L (1 ≤ L ≤ 10), H (1 ≤ H ≤ 100), W (1 ≤ W ≤ 100), N (1 ≤ N ≤ 100) и S (1 ≤ S ≤ 10000), обозначающих количество этажей, высоту и ширину каждого этажа, количество потерявших сознание людей и заданное время соответственно.

Следующие L блоков описывают карту каждого этажа от 1-го до L-го этажа соответственно. Каждый этаж состоит из H строк, каждая из которых содержит W символов. Символы, которые могут появляться на каждом этаже:

• S Точка начала, также служит точкой выхода. Будет только одна точка начала/выхода, и она будет на первом этаже.

• X Препятствие, ячейка, которую нельзя посетить (стена, огонь и т.д.).

• U Лестница, соединяющая с верхним этажом. На том же месте на верхнем уровне будет символ D. Этот символ не появится на самом верхнем уровне здания.

• D Лестница, соединяющая с нижним этажом. На том же месте на нижнем уровне будет символ U. Этот символ не появится на самом нижнем уровне здания.

• . Пустое пространство, ячейка, которую можно посетить.

Следующие N строк каждая содержит четыре целых числа f[i] (1 ≤ f[i] ≤ L), r[i] (1 ≤ r[i] ≤ H), c[i] (1 ≤ c[i] ≤ W), p[i] (1 ≤ p[i] ≤ 1000), обозначающих местоположение каждого добровольца (этаж, рядок, колонка) и количество баллов, назначенных этому добровольцу соответственно. Можно предположить, что каждый доброволец будет находиться в пустом пространстве и ни два добровольца не занимают одно и то же место.

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

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

Примеры