Problem hidden
|This problem was hidden by Editorial Board member probably because it has incorrect language|version or invalid test data, or description of the problem is not clear.|

GARDEN11 - Cerca do Jardim

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


Adicionado por:Wanderley Guimarăes
Data:2012-05-27
Tempo limite:11.55s
Tamanho do fonte:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Linguagem permitida:Todas exceto: ASM64 CLOJURE ERL FSHARP PERL6 PY_NBC SCALA TCL
Origem:Final Sul-Americana da Maratona de Programaçăo da ACM 2011

© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.