나무 울타리

은행에 돈을 맡기면 그 돈이 어떻게 되는지 궁금했던 적이 있나요? 은행은 예금을 금, 주식, 채권, 대출, 다른 은행 예치금 등 여러 자산의 형태로 보유합니다. 여러 차례의 금융 위기를 거치면서 많은 은행은 주식이 믿을 만하지 못하고 보유하기에 너무 위험하다고 판단하게 되었습니다.

그래서 은행들은 다른 자산, 특히 금을 선호합니다. 하지만 금은 전 세계에 존재하는 양이 한정되어 있어, 모든 은행이 보유한 돈을 전부 뒷받침하기에는 턱없이 부족합니다.

금이 부족할 때는 다른 상품을 대신 활용해야 합니다. 모네타니아 국제은행은 아주 오래되고 값비싼 나무를 자산으로 삼는 방법을 떠올렸습니다. 은행은 그런 나무 여러 그루가 자라는 땅을 사들였고, 나무의 가치가 말 그대로 자라나기를 기대합니다.

안타깝게도 나무는 갉아먹는 야생동물과 끊임없는 도난 위험에 노출되어 있어, 은행은 나무 둘레에 튼튼한 울타리를 세워야 합니다. 쓸 수 있는 유일한 재료는 나무 그 자체의 목재뿐이므로, 남길 나무를 둘러싸기 위해 일부 나무를 베어 내야 합니다. 가치를 최대한 지키려면 베어 내는 나무의 총 가치를 최소로 만들어야 합니다. 이 최솟값을 구하는 프로그램을 작성하세요.

입력은 여러 개의 테스트 케이스로 이루어지며, 각 케이스는 하나의 땅을 나타냅니다.

각 테스트 케이스의 첫 줄에는 나무의 수를 나타내는 정수 $N$ ($2 \le N \le 16$)이 주어집니다. 이어지는 $N$개의 줄에는 각각 네 정수 $X_i$, $Y_i$, $V_i$, $L_i$가 공백으로 구분되어 주어집니다.

• $(X_i, Y_i)$는 평면에서 나무 $i$의 위치이며, $-10,000 \le X_i, Y_i \le 10,000$입니다.
• $V_i$는 그 나무의 가치, $L_i$는 그 나무의 목재로 세울 수 있는 울타리의 길이이며, $0 \le V_i, L_i \le 10,000$입니다.

한 테스트 케이스 안에서 같은 위치에 서 있는 나무는 없습니다. 입력은 $N$ 자리에 $0$이 주어지는 줄로 끝나며, 이 줄은 어느 테스트 케이스에도 포함되지 않습니다.

각 테스트 케이스마다, 베어 낸 나무에서 얻은 목재의 길이(그 나무들의 $L_i$의 합)가 남은 모든 나무를 감싸는 하나의 연속된 울타리를 세우기에 충분하도록 나무의 부분집합을 골라 베어 냅니다. 그런 선택 중에서 베어 낸 나무들의 가치 합이 가장 작은 경우를 찾습니다.

모든 나무는 지름이 $0$인 점으로 간주합니다. 그러면 남은 나무를 감싸는 울타리의 길이는 그 점들의 볼록 껍질(convex hull) 둘레와 같으며, 다음의 퇴화 경우를 따릅니다. 남은 나무가 없거나 한 그루뿐이면 필요한 길이는 $0$이고, 남은 나무가 정확히 두 그루이거나 남은 나무가 모두 한 직선 위에 있으면 필요한 길이는 그들을 잇는 선분 길이의 두 배입니다.

각 테스트 케이스마다 다음 형식으로 정확히 한 줄을 출력합니다.

The lost value is T.

여기서 $T$는 베어 내야 하는 나무들의 최소 총 가치입니다.