Задача №397. Цена и длина
В саду растут деревья. У каждого есть цена и длина. Чтобы построить забор какой-то длины L, нужно срубить деревьев с суммарной длиной L или больше. Нужно, срубив некоторые деревья, построить забор вокруг оставшихся. При этом нужно потратить как можно меньше денег. Если таких способов несколько, нужно выбрать тот, в котором деревьев рубится меньше. Если и таких несколько, выведите любой. Деревья считаются имеющими нулевой радиус.
Во входном файле записано число деревьев N (2 <= N <= 14), а затем каждое дерево описано четырьмя числами xi, yi, vi, li - координаты (целые от -10000 до 10000), цена и длина (от 0 до 10000).
В выходной файл выведите номера деревьев, которые необходимо срубить, а также излишек срубленного материала. Формат выходных данных - см. примеры выходных файлов.
5 0 0 1000 11 0 3 1000 11 3 0 1000 11 3 3 1000 11 1 1 100 12
Cut these trees: 5 Extra wood: 0.00
2 100 100 100 100 0 1 100 100
Cut these trees: 1 Extra wood: 100.00