SPOJ Brasil

Gary é um jardineiro cuidadoso que possui um campo retangular repleto de árvores. Existem dois tipos de árvores em suas terras: pinheiros e larícios. Para melhorar suas vitalidades, ele decidiu começar a usar um fertilizante específico para cada tipo de árvore, em vez do fertilizante genérico que ele estava usando até agora.

Como Gary possui muitas árvores, fertilizantes não podem ser colocados individualmente em cada árvore. Por este motivo ele decidiu construir uma cerca que separa o campo em dois, e usar o fertilizante de pinheiro em um lado e o fertilizante de larício no outro lado. A nova cerca será construída sobre uma linha reta conectando dois pontos distintos localizados na fronteira das terras.

Infelizmente, cada fertilizante é ótimo para o tipo de árvore que ele foi projetado, mas mortal para o outro. Depois de construir a cerca e decidir que fertilizante ele irá usar em cada lado, os larícios do lado dos pinheiros e os pinheiros do lado dos larícios serão derrubados, para previnir uma morte lenta que irá arruinar a paisagem. Além disso, antes de construir a cerca é necessário derrubar qualquer árvore que esteja exatamente sobre a linha onde a cerca será construída.

É claro, Gary ama suas árvores. Dependendo do seu tipo, idade e outros fatores, cada árvore possui um certo valor. O jardineiro quer construir a cerca e selecionar onde usar cada fertilizante de tal modo que sua perda seja minimizada, onde a perda é a soma dos valores das árvores que serão derrubadas.

Você foi contratado para construir a cerca. Antes de começar seu trabalho, diga a Gary quanto ele perderá quando escolher otimamente a localização da cerca e o fertilizante para cada lado.

Entrada

Cada caso de teste é descrito usando várias linhas. A primeira linha, contém dois inteiros P e L, representando respectivamente o número de pinheiros e larícios (1 ≤ P,L ≤ 1000). Cada uma das próximas P linahs descreve um pinheiro. Depois disso, cada uma das L linhas seguintes descreve um larício. As árvores são modeladas como pontos no plano XY. Cada árvore é descrita usando três inteiros X, Y e V , onde X e Y são as coordenadas da árvore (-105 ≤ X,Y ≤ 105), e V é seu valor (1 ≤ V ≤ 1000): Você pode assumir que em cada caso de teste duas árvores não terão a mesma localização.

O último caso de teste é seguido por uma linha contendo dois zeros.

Saída

Para cada caso de teste imprima uma linha com um inteiro representando a mínima perda possível para o jardineiro.

Exemplo

Entrada

2 3 
2 2 10 
4 4 10 
2 4 10 
4 2 10 
3 3 10 
2 3 
2 2 20 
4 4 20 
2 4 10 
4 2 10 
3 3 10 
1 1 
-10000 -10000 1000 
10000 10000 1000 
2 2 
0 0 4 
0 2 2 
0 1 3 
0 4 1 
4 1 
0 1 1000 
0 -1 1000 
1 0 1000 
-1 0 1000 
0 0 1 
0 0 

Saída

10
20
0
2
1