991. Ил-2

Заинтересовавшись историей ВОВ, Константин задумался над возможностями перелетов знаменитых штурмовиков Ил-2. К примеру, пусть на плоскости заданы своими координатами и запасом единовременно выделяемого горючего `N` аэродромов (`1\ ≤\ N\ ≤\ 15`). В Вашем распоряжении самолет с 1000 литрами горючего. 1 литр горючего тратится на преодоление 1 км. Ваша задача: из исходной точки с координатами (0, 0) достичь последнего в списке аэродрома, совершив как можно меньше посадок, или установить, что перелет невозможен. Вы можете неограниченное число раз приземляться на каждом из аэродромов. При этом к запасам горючего на самолете будет добавлено горючее, выделяемое на аэродроме. Однако количество горючего, которое несет самолет в каждый момент времени, не может превышать емкости топливных баков, т.е. 1000 л. Каждый раз, садясь на аэродром, летчик получает соответствующую норму горючего, даже если неоднократно садился на этот аэродром. Запрещено садиться на один и тот же аэродром два раза подряд. Беспосадочный перелет между двумя точками можно совершить, если расстояние между ними (выраженное в километрах, округленное до меньшего ближайшего целого), не превосходит количества горючего (выраженного в литрах), которое несет самолет в данный момент. Затраты горючего на перелет всегда целые и равны расстоянию между аэродромами, округленному до меньшего ближайшего целого.

На первой строке – число `N`. Следующие `N` строк содержат по три неотрицательных целых числа `x`, `y`, `f`, где `0\ ≤\ x,\ y\ ≤\ 30000` – координаты аэродрома, `0\ ≤\ f\ ≤\ 1000` – норма выделяемого горючего. Аэродром не может быть в точке `(0,\ 0)`.

Минимальное количество посадок, или число 0, если перелет невозможен.

2
1000 0 250
1250 0 0

2