시간 제한메모리 제한제출정답맞힌 사람정답 비율
5 초 128 MB198535.714%

문제

Gary is a careful gardener that has a rectangular field full of trees. There are two kinds of trees in his land: pines and larches. To improve their vitality, he decided to start using a specific fertilizer for each kind of tree, instead of the generic fertilizer he was using so far.

Since Gary has many trees, fertilizers cannot be placed individually on each tree. For this reason he decided to build a fence to separate the field in two, and use the pine fertilizer on one side and the larch fertilizer on the other side. The new fence will be built over a straight line connecting two distinct points located on the boundary of the land.

Sadly, each fertilizer is great for the kind of tree it is intended, but deadly for the other. After building the fence and deciding which fertilizer will be used on each side, larches in pines’ side and pines in larches’ side will be cut down, to prevent a slow death that will ruin the landscape. Furthermore, before building the fence it is necessary to cut down trees of any kind lying directly over the line where the fence will be located.

Of course, Gary loves his trees. Depending on their kind, age and other factors, each tree has a certain value. The gardener wants to build the fence and select where to use each fertilizer in such a way that his loss is minimized, where the loss is the sum of the values of the trees that will be cut down.

You were hired to build the fence. Before starting your work, tell Gary how much he will lose when choosing optimally the location of the fence and the fertilizer for each side.

입력

Each test case is described using several lines. The first line contains two integers P and L, representing respectively the number of pines and the number of larches (1 ≤ P, L ≤ 1000). Each of the next P lines describes a pine. After that, each of the next L lines describes a larch. Trees are modeled as points in the XY plane. Each tree is described using three integers X, Y and V , where X and Y are the coordinates of the tree (−105 ≤ X, Y ≤ 105), and V is its value (1 ≤ V ≤ 1000). You may assume that within each test case no two trees have the same location.

The last test case is followed by a line containing two zeros.

출력

For each test case output a line with an integer representing the minimum possible loss for the gardener.

예제 입력 1

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

예제 출력 1

10
20
0
2
1

출처

ICPC > Regionals > Latin America > Latin America Regional Contests 2011 G번

  • 문제를 만든 사람: Pablo Ariel Heiber