题目描述

你正在玩一个硬币谜题。这个谜题的规则如下：

桌上有 $N$ 个硬币。第 $i$ 个硬币是一个半径为 $r_i$ 的圆，初始位置在 $(sx_i, sy_i)$ 处。每个硬币还有一个目标位置：你需要将第 $i$ 个硬币移动到 $(tx_i, ty_i)$ 处。你可以逐个移动硬币，并且每个硬币最多只能移动一次。当你移动硬币时，它必须沿着直线从初始位置移动到目标位置。此外，硬币在移动过程中不能与其他硬币碰撞。

谜题的得分是你将硬币从初始位置移动到目标位置的硬币数量。你的任务是编写一个程序，确定给定谜题实例的最大得分。

输入

输入由一个测试用例组成，格式如下：

$N$ $r_{1}$ $sx_{1}$ $sy_{1}$ $tx_{1}$ $ty_{1}$ $\vdots$ $r_{N}$ $sx_{N}$ $sy_{N}$ $tx_{N}$ $ty_{N}$

第一行包含一个整数 $N$ ($1 \leq N \leq 16$)，表示谜题中使用的硬币数量。接下来的 $N$ 行中，每行包含五个整数：$r_i$、$sx_i$、$sy_i$、$tx_i$ 和 $ty_i$ ($1 \leq r_i \leq 1{,}000$, $-1{,}000 \leq sx_i, sy_i, tx_i, ty_i \leq 1{,}000$, $(sx_i, sy_i) \neq (tx_i, ty_i)$)。它们描述了第 $i$ 个硬币的信息：$r_i$ 是第 $i$ 个硬币的半径，$(sx_i, sy_i)$ 是第 $i$ 个硬币的初始位置，$(tx_i, ty_i)$ 是第 $i$ 个硬币的目标位置。

你可以假设硬币在初始位置时不会相互接触或重叠。你还可以假设即使每个硬币的半径变化 $10^{-5}$，最大得分也不会变化。

输出

打印给定谜题实例的最大得分。

示例输入1

3
2 0 0 1 0
2 0 5 1 5
4 1 -10 -5 10

示例输出1

2

示例输入2

3
1 0 0 5 0
1 0 5 0 0
1 5 5 0 5

示例输出2

3

示例输入3

4
1 0 0 5 0
1 0 5 0 0
1 5 5 0 5
1 5 0 0 0

示例输出3

0

注意

在第一个示例中，第三个硬币无法移动，因为它被其他两个硬币所挡住。

示例1. 初始位置

示例1. 移动后的位置