eolymp
bolt
Try our new interface for solving problems
Problems

Расширенный кегельбан

Расширенный кегельбан

Time limit 1 second
Memory limit 16 MiB

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

Игровая площадка представляет собой прямоугольную область, имеющую по горизонтали nX клеток, а по вертикали nY клеток. В каждой из клеток,кроме клеток нижнего ряда, может располагаться один из видов объектов:

  • кегля с написанным на ней числом;

  • бомба;

  • отражательный переключатель;

  • яма.

В одной из клеток нижнего ряда помещается мяч, который можно толкнуть вверх либо вертикально, либо под углом 45° вправо или влево. При достижении мячом крайней левой или крайней правой клетки какого-либо ряда (за исключением случая, если он движется вертикально), он меняет знак горизонтальной составляющей вектора движения. При достижении мячом клетки верхнего ряда меняется знак вертикальной составляющей вектора движения. При достижении мячом клетки нижнего ряда игра заканчивается.

При попадании мяча в квадрат, в котором есть объект, в зависимости от вида объекта выполняются следующие действия:

  • если объектом является кегля, то число, записанное на ней, добавляется к результату игры, а сама кегля удаляется с площадки;

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

  • если объектом является отражательный переключатель, то меняется знак вертикальной составляющей вектора движения;

  • если объектом является яма, то движение мяча останавливается и игра заканчивается.

Если в какой-либо момент времени производится "зацикливание" мяча в некоторой области площадки, то игра заканчивается.

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

Input data

Первая строка содержит два целых числа nX и nY, разделенных пробелом – размер игровой площадки по горизонтали и вертикали (2nX100, 2nY100).

Вторая строка содержит целое число N – количество объектов, размещенных на игровой площадке (1NnX·(nY-1)).

Следующие N строк содержат описание одного объекта в виде трех элементов oXoY Z, разделенных пробелами, где oX и oY – координаты объекта (1oXnX, 2oYnY), а Z содержит информацию, описывающую объект:

  • если объектом является кегля, то число, записанное на ней (в диапазоне от 1 до 100);

  • если объектом является бомба, то символ "*" (без кавычек);

  • если объектом является отражательный переключатель, то символ "-" (без кавычек);

  • если объектом является яма, то символ "+" (без кавычек).

Все пары oX, oY уникальны.

Output data

Выходной файл должен содержать одно целое число – максимальный результат, который может быть получен в игре.

Examples

Input example #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
Output example #1
28
Source Региональная олимпиада по программированию, СибГИУ, 2011