Робот-пилосос#11014
Професор для автоматизації прибирання кімнати вирішив змайструвати робот-пилосос. Робот-пилосос за допомогою датчиків сканує приміщення і визначає рівень забруднення у ньому, складаючи матрицю забрудненості.
За заданою матрицею забрудненості визначте, з якого місця потрібно почати прибирання кімнати, щоб зібрати як можна більше бруду. Відомо кількість переміщень, яку може зробити робот-пилосос та циклічний алгоритм роботи робота-пилососа, який задається текстовим рядком, що складається з літер R (вправо), L (вліво), U (вгору), D (донизу). У випадках, коли робот-пилосос досягає границі кімнати і намагається зробити крок у стіну, виконується крок у протилежну сторону.
Визначте, скільки максимально бруду зможе зібрати робот-пилосос і у якій клітинці його потрібно розмістити.
У першому рядку задачі числа та – висота та ширина кімнати (2 \le N, M \le 100).
У другому рядку записано число – кількість кроків, яку робить робот-пилосос (1 \le K \le 10\,000).
Третій рядок містить послідовність, що задає алгоритм рухів робота-пилососа.В наступних рядках знаходиться по чисел – рівень забрудненості у відповідній клітинці P_{ij} (0 \le P_{ij} \le 100).
В одному рядку виведіть три числа через пробіл: максимальну кількість бруду, яку може зібрати робот-пилосос, номер рядка та номер стовпця клітинки, де потрібно розмістити робот-пилосос.
Якщо таких клітинок декілька, то виберіть ту, що має найменшу суму індексів, якщо і таких декілька, то ту, що розташована ближче до лівої сторони кімнати.
Приклад 1
Розмістивши робот-пилосос у клітинці , він одразу збирає одиниць сміття, далі виконує поступово чотири кроки вправо (RRRR), збираючи сумарно одиниці сміття. Оскільки робот тепер знаходиться біля стіни і зробити крок вправо неможливо (R), то виконується крок у протилежну сторону (L), але дана клітинка вже почищена від сміття. Далі залишається виконати останній крок вправо (R) у клітинку, яка теж вже почищена.
Робот пройде таку послідовність клітинок:
R -> R -> R -> R -> R L -> R -> .