Problema B - Faraó
O poderoso faraó Ramsoni decidiu mandar construir duas pirâmides, uma para lhe servir de túmulo a ele e outra para a sua esposa, a rainha Nefertitioi. Ele quer que as pirâmides sejam enormes, mas há uma pequena dificuldade: o Egipto está tão cheio de pirâmides, que já há pouco espaço para construir mais.
Escreva um programa que dado um mapa rectangular no Egipto onde estão assinaladas todas as pirâmides existentes, calcule o máximo volume combinado das duas pirâmides que se podem construir nos espaços ainda livres. Dito de outro modo, de todos os pares de novas pirâmides possíveis, queremos escolher aquelas cuja soma dos volumes seja o maior possível. Todas as pirâmides (as já construídas e estas novas) têm base quadrada e a altura é igual ao lado da base. Recorde que o volume da pirâmide é um terço da área da base vezes a altura.
Na primeira linha vêm dois números, B e H, representado o medida da base e a medida da altura do rectângulo que contém o mapa do Egipto, em decâmetros (1 ≤ B, H ≤ 300). Na segunda linha, vem um número N, o número de pirâmides já construídas (0 ≤ N ≤ 100). Nas N linhas seguintes vêm três números, X, Y e L, descrevendo cada uma das pirâmides: X é a coordenada horizontal do canto inferior esquerdo da base da pirâmide, Y é a coordenada vertical desse ponto e L é o comprimento do lado da base da pirâmide (que é igual à altura). Uma unidade representa um decâmetro. Em todos os casos, temos 0 ≤ X ≤ B - L, 0 ≤ Y ≤ H - L e 1 ≤ L ≤ 300. Todos os rectângulos são disjuntos, dois a dois, mas podem tocar-se nos lados ou nos cantos.
Uma única linha, na qual existe um único número: o volume, em decâmetros cúbicos, das duas pirâmides que em conjunto são mais volumosas e que se podem construir no espaço livre no Egipto (nota que as pirâmides são disjuntas, mas podem tocar noutras pirâmides nos lados ou nos cantos). Em todos os casos de teste, é sempre possível construir duas pirâmides. Pode existir mais do que um par que dê o volume máximo. O número deve ser escrito arredondado a duas casas decimais.