acm

cz

acm

cz

Dept. of Computer Science and Engineering, Czech Technical University in Prague

Faculty of Mathematics and Physics, Charles University in Prague

Faculty of Electrical Engineering and Computer Science, Technical University of Ostrava

Faculty of Informatics and Information Technologies, Slovak University of Technology

Faculty of Informatics, Masaryk University

Faculty of Management Science and Informatics, University of Zilina

CTU Open Contest 2008

Wooden Fence

fence.c, fence.C, fence.java, fence.p

Did you ever wonder what happens to your money when you deposit them to a bank account.

All banks hold such deposits in various assets, such as gold, stocks, obligations, deposits in other

banks, loans, bonds, and many others. Due to the financial crisis and instability of the stock

exchanges, many banks find out that stocks are not very reliable and their possession may be

too risky.

Therefore, the banks now prefer other assets, especially gold. The main trouble with gold is

that there is only a limited amount of it in the whole world. And it is not enough to cover all

money held by all banks. (Wait, isn’t this the real reason of the crisis.)

If there is not enough gold, other commodities must be exploited instead. The International

Bank of Monetania (IBM) has recently come up with an idea of using very old and valuable

trees as their assets. They bought a piece of land with several such trees and now expect their

value to grow. Literally, of course.

Unfortunately, the trees are threatened by wildlife, because animals do not understand their

value and nibble them. Moreover, there is a permanent danger of theft. As a result, it is

absolutely necessary to build a good solid fence around the trees.

The IBM quickly realized that the only suitable material available to build the fence is the wood

from the trees themselves. In other words, it is necessary to cut down some trees in order to

build a fence around the remaining ones. Of course, to keep the maximum value, we want to

minimize the value of the trees that had to be cut. You are to write a program that solves this

problem.

Input Specification

The input contains several test cases, each of which describes one piece of land. Each test case

begins with a line containing a single integer N,2. N . 16, the total number of trees. Each

of the subsequent N lines contains 4 integers X

i

, Y

i

, V

i

, L

i

separated by at least one space.

The four numbers describe a single tree. (X

i

,Y

i

) is the position of the tree in the plane, V

i

is

its value, and L

i

is the length of fence that can be built using the wood of the tree. You may

assume that 0 . V

i

,L

i

. 10 000 and -10 000 . X

i

,Y

i

. 10 000. No two trees in a test case will

grow at the same position.

The input ends with a line containing zero in place of N.

Output Specification

For each test case, compute a subset of the trees such that, using the wood from that subset, the

remaining trees can be enclosed in a single continuous fence. Find the subset with the minimal

total value. For simplicity, regard the trees as having zero diameter.

Output one line with the sentence “The lost value is T .", where T is the minimal value of

the trees that must be cut.

Sample Input

6

0083

1432

2171

4123

3546

2398

3

30103

5-32025

7-33032

2

100054

0 100 4 5

5

0 0 10 10

0 1 10 10

1 0 10 10

1 1 10 10

50 50 8 4

0

Output for Sample Input

The lost value is 9.

The lost value is 20.

The lost value is 4.

The lost value is 8.