Розширений боулінг
Усі знають гру "Кегельбан", де м'ячем збивають кеглі. "Розширений кегельбан" має ту ж мету, але з додатковими елементами, які ускладнюють гру і роблять її цікавішою.
Ігровий майданчик — це прямокутна область з nX клітинками по горизонталі та nY клітинками по вертикалі. У кожній клітинці, крім клітинок нижнього рядка, може бути один з таких об'єктів:
кегля з числом;
бомба;
відбивальний перемикач;
яма.
М'яч розміщується в одній з клітинок нижнього рядка і може бути штовхнутий вгору: вертикально або під кутом 45° вправо чи вліво. Якщо м'яч досягає крайньої лівої або правої клітинки рядка (крім випадку вертикального руху), змінюється знак горизонтальної складової вектора руху. При досягненні верхнього рядка змінюється знак вертикальної складової вектора руху. Гра закінчується, коли м'яч досягає нижнього рядка.
При потраплянні м'яча в клітинку з об'єктом, виконуються такі дії залежно від об'єкта:
якщо це кегля, число на ній додається до результату, а кегля зникає;
якщо це бомба, вона "вибухає" і знищує всі об'єкти в сусідніх клітинках по горизонталі, вертикалі або діагоналях. Якщо знищується відбивальний перемикач або яма, клітинка стає порожньою. Якщо знищується кегля або бомба, виконуються ті ж дії, що і при потраплянні м'яча в ці об'єкти;
якщо це відбивальний перемикач, змінюється знак вертикальної складової вектора руху;
якщо це яма, рух м'яча зупиняється і гра закінчується.
Якщо м'яч потрапляє в "зациклення" в певній області, гра закінчується.
Потрібно визначити максимальний можливий результат гри, враховуючи, що м'яч може бути розміщений у будь-якій клітинці нижнього рядка.
Вхідні дані
Перша рядок містить два цілі числа nX і nY, розділених пробілом — розмір ігрового майданчика по горизонталі і вертикалі (2 ≤ nX ≤ 100, 2 ≤ nY ≤ 100).
Друга рядок містить ціле число N — кількість об'єктів на майданчику (1 ≤ N ≤ nX·(nY-1)).
Наступні N рядків описують об'єкт у вигляді трьох елементів oX oY Z, розділених пробілами, де oX і oY — координати об'єкта (1 ≤ oX ≤ nX, 2 ≤ oY ≤ nY), а Z описує об'єкт:
якщо це кегля, то число на ній (від 1 до 100);
якщо це бомба, то символ "*" (без лапок);
якщо це відбивальний перемикач, то символ "-" (без лапок);
якщо це яма, то символ "+" (без лапок).
Усі пари oX, oY унікальні.
Вихідні дані
Вихідний файл повинен містити одне ціле число — максимальний результат, який можна отримати у грі.