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