Навчальна тривога

Джоко бере участь у навчанні з пожежної безпеки, організованому Пожежним департаментом Джакарти для нових кандидатів у пожежники. Завдання полягає в порятунку волонтерів (які грають роль непритомних людей), що опинилися в пастці в будівлі за обмежений час. Будівля має кілька поверхів, і волонтери розміщені на різних рівнях. Кожному волонтеру присвоєно певну кількість балів. Кандидат у пожежники повинен врятувати волонтерів, доставивши їх до виходу, і отримує бали за кожного врятованого.

Кожен поверх будівлі можна уявити як сітку клітин. Кожна клітина може бути перешкодою, порожнім простором, сходами або точкою входу/виходу.

Кандидат починає з точки входу, яка є лише в одній клітині на першому поверсі будівлі. Він може переміщатися до будь-якої сусідньої неперешкодженої клітини (на північ, південь, захід або схід) або підніматися чи спускатися сходами за 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), що позначають місцезнаходження кожного волонтера (поверх, рядок, стовпець) та бали, присвоєні цьому волонтеру. Ви можете припустити, що кожен волонтер розташований у порожньому просторі, і жодні два волонтери не займають одне й те саме місце.

Вихідні дані

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

Приклади