Description

A secret organization is conducting a military exercise in the desert. The goal is to defuse a bomb hidden in the desert.

The first phase is an airdrop operation. Each paratrooper jumps from a helicopter hovering over the desert in a fixed order. Upon landing, each paratrooper stays at his landing point.

Each paratrooper has a survival radius. If the bomb is at a distance less than or equal to this survival radius, the paratrooper will sacrifice himself to trigger the bomb. The commander wants to send as few paratroopers as possible, but he also wants at least one paratrooper to survive in the worst case.

The entire desert can be modeled as a plane. Each paratrooper’s landing point is a coordinate $(x, y)$, and we denote his survival radius by $r$. All paratroopers’ information is given in the order they jump: when the $i$-th paratrooper jumps, the first $i-1$ paratroopers have already landed.

Your task is to read all paratroopers’ information from standard input and output the minimum number of paratroopers that must be sent.

Input Format

The first line contains an integer $n$ ($2 \le n \le 2000$).

The next $n$ lines: the $i$-th line contains three integers $x_i, y_i, r_i$ ($-1000 \le x_i, y_i \le 1000$, $1 \le r_i \le 5000$), indicating that the $i$-th paratrooper lands at $(x_i, y_i)$ with survival radius $r_i$.

Output Format

If it is impossible to have at least one paratrooper survive, output NIE.

Otherwise, output a single integer: the minimum number of paratroopers that must be sent.

5
2 2 4
7 2 3
4 3 1
5 7 1
8 7 1

4

Hint

In the worst case, the bomb is at $(5, 3)$. The first three paratroopers die, and the fourth survives.

Translated by ChatGPT 5