Прогулка с Барби
ограничение по времени на тест
2 секунды
ограничение по памяти на тест
512 мегабайт
ввод
стандартный ввод
вывод
стандартный вывод

Пляжный Кен счастлив, потому что Стереотипная Барби наконец ответила ему взаимностью и согласилась вместе прогуляться по пляжу!

Пляж представляет собой прямоугольник $$$h \times w$$$. $$$n$$$ клеток пляжа представляют из себя особые места. В некоторых из них лежат валуны и заходить на них нельзя, а в остальных лежат интересные вещицы — ракушки, кораллы и различного рода приятности, увидев которые, Барби увеличит свою симпатию к Кену на какую-то величину. Для каждой клетки известно, пустая она, заполнена валуном, или там лежит что-то интересное — то есть, при проходе по этой клетке $$$(i, j)$$$, симпатия Барби к Кену увеличится на $$$c_{i,j}$$$. Помогите Кену составить оптимальный маршрут прогулки, чтобы в конце симпатия Барби была максимальна.

Прогулка начинается в точке $$$(1, 1)$$$ и заканчивается в точке $$$(h, w)$$$. Так как у Барби не очень много времени, они могут гулять только влево, вправо и вниз по пляжу.

Входные данные

В первой строке входных данных дано три целых числа — $$$h$$$, $$$w$$$ и $$$n$$$ — высота и ширина пляжа и количество особенных мест ($$$1 \le h \le 10^5$$$; $$$1 \le w \le 10^9$$$; $$$1 \le n \le 10^5$$$).

В следующих $$$n$$$ строках дано описание особых мест. Описание особого места представляется или как $$$i j + d$$$, если на пляже в строке $$$i$$$ и столбце $$$j$$$ стоит лежит вещь, приносящая $$$+d$$$ к симпатии, или $$$i j \#$$$, если в клетке $$$i$$$, $$$j$$$ располагается валун ($$$1 \le d \le 10^9$$$).

Выходные данные

В единственной строке выведите ответ на задачу  — максимальная симпатия, которой Кен может добиться от Барби в конце прогулки (изначально симпатия $$$0$$$).

Гарантируется, что существует какой-то способ добраться из точки $$$(1, 1)$$$ в точку $$$(h, w)$$$.

Пример

Входные данные
4 5 11
1 3 + 2
1 5 #
2 2 + 4
2 3 #
3 1 + 1
3 2 + 1
3 4 #
3 5 + 5
4 1 + 10
4 2 #
4 4 + 2
Выходные данные
10