Matcom Online Grader

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 \leq P, L \leq 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 $(−10^5 \leq X, Y \leq 10^5)$, and V is its value $(1 \leq V \leq 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.