Пляжный Кен счастлив, потому что Стереотипная Барби наконец ответила ему взаимностью и согласилась вместе прогуляться по пляжу!
Пляж представляет собой прямоугольник $$$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