코인 슬라이더

동전 퍼즐을 푼다. 규칙은 다음과 같다.

탁자 위에 동전 $N$개가 놓여 있다. $i$번째 동전은 반지름이 $r_i$인 원이고, 처음에는 중심이 $(sx_i, sy_i)$에 있다. 각 동전에는 목표 위치가 하나씩 있다. $i$번째 동전은 중심이 $(tx_i, ty_i)$에 오도록 옮겨야 한다. 동전은 한 번에 하나씩 옮기고, 각 동전은 최대 한 번만 옮길 수 있다. 동전을 옮길 때는 처음 위치에서 목표 위치까지 직선을 따라 이동해야 한다. 또한 이동하는 도중을 포함해서 동전끼리 충돌해서는 안 된다.

퍼즐의 점수는 처음 위치에서 목표 위치로 옮긴 동전의 개수이다. 주어진 퍼즐에서 얻을 수 있는 최대 점수를 구하는 프로그램을 작성하시오.

입력은 테스트 케이스 하나로 이루어지며 형식은 다음과 같다.

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

첫째 줄에 퍼즐에 쓰이는 동전의 개수 $N$ ($1 \le N \le 16$)이 주어진다. 이어지는 $N$개 줄 중 $i$번째 줄에는 정수 다섯 개 $r_i$, $sx_i$, $sy_i$, $tx_i$, $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$는 $i$번째 동전의 반지름, $(sx_i, sy_i)$는 처음 위치, $(tx_i, ty_i)$는 목표 위치이다.

처음 위치에서 동전끼리 맞닿거나 겹치는 일은 없다. 또한 각 동전의 반지름이 $10^{-5}$만큼 달라져도 최대 점수는 바뀌지 않는다.

주어진 퍼즐의 최대 점수를 한 줄에 출력한다.

첫 번째 예제에서 세 번째 동전은 나머지 두 동전에 막혀 옮길 수 없다.

예제 1. 처음 위치

예제 1. 이동 후