Coin Slider

You are playing a coin puzzle. The rules are as follows.

There are $N$ coins on a table. The $i$-th coin is a circle of radius $r_i$, and its center is initially at $(sx_i, sy_i)$. Each coin also has a target position: you have to move the $i$-th coin so that its center is at $(tx_i, ty_i)$. You move coins one at a time, and you can move each coin at most once. When you move a coin, it travels from its initial position to its target position along a straight line. In addition, coins must never collide with each other, including in the middle of a move.

The score of the puzzle is the number of coins you move from their initial positions to their target positions. Write a program that determines the maximum score for the given puzzle.

The input consists of a single test case in the following format.

N
r1 sx1 sy1 tx1 ty1
.
.
.
rN sxN syN txN tyN

The first line contains an integer $N$ ($1 \le N \le 16$), the number of coins in the puzzle. The $i$-th of the following $N$ lines contains five integers $r_i$, $sx_i$, $sy_i$, $tx_i$, and $ty_i$ ($1 \le r_i \le 1{,}000$, $-1{,}000 \le sx_i, sy_i, tx_i, ty_i \le 1{,}000$, $(sx_i, sy_i) \ne (tx_i, ty_i)$). $r_i$ is the radius of the $i$-th coin, $(sx_i, sy_i)$ is its initial position, and $(tx_i, ty_i)$ is its target position.

At their initial positions, no two coins touch or overlap. You can also assume that the maximum score does not change even if the radius of every coin changes by $10^{-5}$.

Print the maximum score of the given puzzle on a single line.

In the first example, the third coin cannot move because the other two coins are in its way.

Example 1. Initial positions

Example 1. After the moves