URI Online Judge | 3090

Campo de Batalha

Por Guilherme Londe, PUC Goiás BR Brazil

Timelimit: 1

Uma batalha épica entre dois exércitos inimigos está prestes a iniciar. Os dois exércitos estão distribuídos em um campo de batalha e estão separados entre si por um rio que cruza esse campo.

O campo é um retângulo de comprimento n e largura m. O rio é um segmento de reta com extremidades nos pontos (0, 0) e (nm) e cuja espessura deve ser desconsiderada.  Um soldado é definido pela sua habilidade hi e pelas coordenadas xi e yi  de sua localização inicial. Um soldado pertence ao primeiro exército se está localizado acima do rio, isto é, está contido no triângulo {(0, 0), (0, m), (nm)}, ou pertence ao segundo exército caso contrário. É garantido que nenhum soldado está sob o rio no momento inicial.

O nível de habilidade de um exército é a soma das habilidades de todos os soldados que pertencem a este exército. Escreva um programa que, dada a descrição do campo e de cada soldado, imprime o nível de habilidade de cada exército.

Entrada

A primeira linha da entrada contém três inteiros n, m e s (1 ≤ n, m ≤ 109, 0 ≤ s ≤ 105), em que n e m correspondem ao comprimento e a largura do campo, respectivamente, e s representa o número de soldados no campo no momento inicial. Cada uma das próximas s linhas contém três inteiros, no qual a i-ésima linha contém os valores xi, yi e hi (0 ≤ x≤ n; 0 ≤ yi ≤ m; 0 ≤ hi ≤ 104).

Saída

Imprima uma linha que contém dois inteiros: o nível de habilidade do primeiro exército seguido pelo nível de habilidade do segundo exército, ambos separados por um espaço em branco.

Exemplos de Entrada Exemplos de Saída

3 2 3
0 1 3
1 1 4
2 1 2

7 2

5 9 7
4 8 3
3 0 5
0 8 4
2 4 2
2 3 6
4 7 9
5 8 1

9 21