Məsələlər
Расширенный кегельбан
Расширенный кегельбан
\includegraphics{https://static.e-olymp.com/content/8c/8c8f23ba66c4a7b6966d49a5be73ad3deec36ed0.jpg}
Всем известна игра "Кегельбан", в которой мячом сбиваются кегли. "Расширенный кегельбан" имеет ту же цель, однако в него введен ряд новшеств, усложняющих игру и делающих ее более интересной.
Игровая площадка представляет собой прямоугольную область, имеющую по горизонтали \textbf{nX} клеток, а по вертикали \textbf{nY} клеток. В каждой из клеток, \textbf{кроме клеток нижнего ряда}, может располагаться один из видов объектов:
\begin{itemize}
\item кегля с написанным на ней числом;
\item бомба;
\item отражательный переключатель;
\item яма.
\end{itemize}
В одной из клеток нижнего ряда помещается мяч, который можно толкнуть вверх либо вертикально, либо под углом 45° вправо или влево. При достижении мячом крайней левой или крайней правой клетки какого-либо ряда (\textit{\textbf{за исключением случая, если он движется вертикально}}), он меняет знак горизонтальной составляющей вектора движения. При достижении мячом клетки верхнего ряда меняется знак вертикальной составляющей вектора движения. При достижении мячом клетки нижнего ряда игра заканчивается.
При попадании мяча в квадрат, в котором есть объект, в зависимости от вида объекта выполняются следующие действия:
\begin{itemize}
\item если объектом является кегля, то число, записанное на ней, добавляется к результату игры, а сама кегля удаляется с площадки;
\item если объектом является бомба, то она "взрывается" и уничтожает все объекты, расположенные в соседних с ней клетках по горизонтали, вертикали или диагоналям. При уничтожении отражательного переключателя или ямы на их месте остается пустая клетка. При уничтожении кегли или бомбы выполняются те же действия, что и при попадании мяча в клетку с кеглей или бомбой;
\item если объектом является отражательный переключатель, то меняется знак вертикальной составляющей вектора движения;
\item если объектом является яма, то движение мяча останавливается и игра заканчивается.
\end{itemize}
Если в какой-либо момент времени производится "\textit{\textbf{зацикливание}}" мяча в некоторой области площадки, то игра заканчивается.
Требуется определить \textbf{максимальный} результат игры, с учетом того, что изначально мяч может быть помещен в любую клетку нижнего ряда.
\InputFile
Первая строка содержит два целых числа \textbf{nX} и \textbf{nY}, разделенных пробелом -- размер игровой площадки по горизонтали и вертикали (\textbf{2} ≤ \textbf{nX} ≤ \textbf{100}, \textbf{2} ≤ \textbf{nY} ≤ \textbf{100}).
Вторая строка содержит целое число \textbf{N} -- количество объектов, размещенных на игровой площадке (\textbf{1} ≤ \textbf{N} ≤\textbf{nX}·(\textbf{nY-1})).
Следующие \textbf{N} строк содержат описание одного объекта в виде трех элементов \textbf{oX} \textbf{oY Z}, разделенных пробелами, где \textbf{oX} и \textbf{oY} -- координаты объекта (\textbf{1} ≤ \textbf{oX} ≤ \textbf{nX}, \textbf{2} ≤ \textbf{oY} ≤ \textbf{nY}), а \textbf{Z} содержит информацию, описывающую объект:
\begin{itemize}
\item если объектом является кегля, то число, записанное на ней (в диапазоне от \textbf{1} до \textbf{100});
\item если объектом является бомба, то символ "\textbf{*}" (без кавычек);
\item если объектом является отражательный переключатель, то символ "\textbf{-}" (без кавычек);
\item если объектом является яма, то символ "\textbf{+}" (без кавычек).
\end{itemize}
Все пары \textbf{oX}, \textbf{oY} уникальны.
\OutputFile
Выходной файл должен содержать одно целое число -- максимальный результат, который может быть получен в игре.
Giriş verilənləri #1
6 9 8 1 8 + 2 7 7 3 6 * 3 8 1 4 5 16 5 6 5 5 8 - 6 2 23
Çıxış verilənləri #1
28