MOJ Round #3Ended |
La ciudad de Pinar del Rio está diseñada para ser una ciudad fácil de entender. Pinar del Rio está conformada por calles de una sola dirección; $N$ calles van del sur hacia el norte y $M$ van del oeste al este. Las calles están numeradas de $1$ a $N$ comenzando por el oeste y de $1$ a $M$ comenzando desde el sur. El diseño es casi idéntico al cuadrante positivo de un plano de dos dimensiones. En exactamente $K$ intersecciones de las calles hay tiendas de dulces, cada una de ellas con una reserva de cierta cantidad de caramelos. El chico de nuestra historia está ayudando en la preparación del cumpleaños de su hermana, es por esto que necesita recopilar la mayor cantidad de dulces posible. Él comenzará a partir de su casa en la posición $(0, 0)$ (que es la esquina sur-oeste de la ciudad) y tratará de visitar las tiendas de dulces en la ciudad sin violar las normas de tráfico, esto lo hace conduciendo solamente hacia el norte o al este. ¿Cuál es la máxima cantidad de dulces que él será capaz de recopilar?
Dos enteros $N$, $M$, el número de calles que van del sur al norte y el número de calles que van del oeste al este respectivamente. Seguirán $K$ líneas representando las tiendas de dulces en la ciudad con tres enteros $x_i$, $y_i$, $c_i$ describiendo que en la intersección $(x_i, y_i)$ se encuentra una tienda que tiene Ci caramelos.
$1 \le N, M \le 10^9$
$1 \le K \le 10^5$
$1 \le x_i \le N$
$1 \le y_i \le M$
$1 \le c_i \le 10^4$
La máxima cantidad de caramelos que el muchacho de nuestra historia será capaz de obtener.