Увы! Колдун быстро обнаружил, что единственный подходящий материал для постройки забора – это сами деревья. Другими словами, необходимо срубить некоторые деревья для того, чтобы построить забор вокруг оставшихся. Естественно, чтобы сберечь свою голову, колдун захотел минимизировать стоимость срубленных деревьев. Он поднялся в свою башню и оставался там до тех пор, пока не придумал наилучшее возможное решение.

Вы должны написать программу, решающую задачу, с которой столкнулся главный королевский колдун. Постройте такое подмножество деревьев с наименьшей суммарной стоимостью, что, срубив деревья из этого подмножества, можно построить один забор, огораживающий все оставшиеся деревья. Если существует более одного подмножества с минимальной стоимостью, выберите то, в котором меньше деревьев.

Входные данные
В первой строке входного файла записано целое число N – количество деревьев в королевском лесу (2 ≤ N ≤ 14). Деревья нумеруются
последовательными целыми числами от 1 до N. Каждая из последующих N строк содержит четыре целых числа x_i, y_i, v_i, l_i, описывающих очередное дерево. (x_i, y_i) – это координаты дерева на плоскости, v_i – его стоимость, а l_i – длина забора, который может быть построен из этого дерева. Все числа v_i, l_i, а также абсолютные величины x_i и y_i – целые числа из диапазона [0, 10000]. Считается, что деревья имеют нулевой радиус.

Выходные данные
Первая строка выходного файла должна содержать номера деревьев, которые необходимо срубить, разделенные пробелом. Во вторую строку выведите излишек срубленного материала c 2 знаками после десятичной точки.

Пример входного файла
6
0 0 8 3
1 4 3 2
2 1 7 1
4 1 2 3
3 5 4 6
2 3 9 8

Пример выходного файла
2 4 5
3.16

Решение

Для решения этой задачи будем перебирать все возможные подмножества деревьев для рубки. Для каждого анализируемого подмножества M нужно найти выпуклую оболочку оставшихся деревьев и проверить, что ее периметр не превышает длины забора, который мы можем построить из деревьев M. Рассмотрев все такие подмножества M, выберем то, которое имеет минимальную суммарную стоимость деревьев.

    Для сокращения перебора не следует рассматривать подмножества с большей стоимостью, чем стоимость наилучшего из ранее найденных. Поэтому важно быстро найти решение, близкое к оптимальному.