Coin Slider

Time limit2sMemory limit512 MB

Summary

Choose the largest subset of at most 16 coins and an order of moves so no moving coin ever collides with a stationary or already-moved coin.

Level: Hard8 of 10
Topics: Geometry, Bit manipulation, Dynamic programming, Greedy
Solved: No attempts yet

Problem

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.

Input

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}$ .

Output

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

Hint

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

Examples3

Example 1
Input
```
3
2 0 0 1 0
2 0 5 1 5
4 1 -10 -5 10
```
Expected output
```
2
```
Example 2
Input
```
3
1 0 0 5 0
1 0 5 0 0
1 5 5 0 5
```
Expected output
```
3
```

Example 3

Input

Expected output