Wooden Fence

Have you ever wondered what happens to your money when you deposit it in a bank? Banks hold deposits in many kinds of assets — gold, stocks, bonds, loans, deposits in other banks, and more. After repeated financial turmoil, many banks have decided that stocks are unreliable and too risky to hold.

Banks therefore prefer other assets, above all gold. The trouble with gold is that only a limited amount of it exists in the whole world — not nearly enough to back all the money held by every bank.

When gold runs short, other commodities must be used instead. The International Bank of Monetania has come up with the idea of using very old and valuable trees as assets. It bought a plot of land holding several such trees and expects their value to grow — literally.

Unfortunately, the trees are threatened by wildlife that nibbles at them and by the constant danger of theft, so the bank must build a strong fence around them. The only suitable building material available is the wood of the trees themselves, so some trees have to be cut down in order to fence in the rest. To preserve as much value as possible, we want to minimize the total value of the trees that are cut down. Write a program that computes this minimum.

The input contains several test cases, each describing one plot of land.

Each test case begins with a line containing a single integer $N$ ($2 \le N \le 16$), the number of trees. Each of the next $N$ lines contains four integers $X_i$, $Y_i$, $V_i$, $L_i$, separated by whitespace:

• $(X_i, Y_i)$ is the position of tree $i$ in the plane, with $-10,000 \le X_i, Y_i \le 10,000$;
• $V_i$ is the tree's value and $L_i$ is the length of fence that can be built from its wood, with $0 \le V_i, L_i \le 10,000$.

No two trees in a test case stand at the same position. The input ends with a line containing $0$ in place of $N$; that line is not part of any test case.

For each test case, choose a subset of trees to cut down so that the wood taken from them — the sum of their $L_i$ — is long enough to build a single continuous fence around all of the remaining trees. Among all valid choices, pick the one whose cut-down trees have the smallest total value.

Treat every tree as a point of zero diameter. The fence around the remaining trees then has the length of the perimeter of their convex hull, with these degenerate cases: if no tree or exactly one tree remains, the required length is $0$; if exactly two trees remain, or all remaining trees are collinear, the required length is twice the length of the segment that spans them.

For each test case, print one line in exactly this form:

The lost value is T.

where $T$ is the minimum total value of the trees that must be cut down.