경곽의 자랑 고무고무요한(줄여서 GM요한)의 이름은 똑바로 읽어도 거꾸로 읽어도 배요배다. 

GM요한은 겨울을 맞아 학술정보관에 배치된 N개의 크리스마스트리를 보았다. 코딩하는 사람으로서 이파리가 위쪽을 향해 있는 모양의 트리를 참을 수 없었던 GM요한은 화가 나서 통제할 수 없는 상태가 되었다. 

GM요한은 크리스마스트리들을 바닥에서 뽑아 트리의 바닥을 천장에 붙여 진정한 트리의 모양을 완성하려고 한다. 

크리스마스트리는 크게 받침대와 나무로 구성되는데, i번째 트리의 받침대는 지름이 2R_i인 다이아몬드의 모양을 가지고 있다. GM요한이 바닥에 있는 크리스마스트리를 천장에 붙일 때, 좌우로는 이동시키지 않기로 했다. 

학술정보관 1층 복도와 천장은 각각 2차원 평면으로 나타낼 수 있으며, i번째 크리스마스트리의 받침대의 중심의 좌표는 (Xi, Yi)로 주어진다. 

또한, 전지전능한 GM요한은 옳게 된 크리스마스트리들의 모양에 흐뭇해하며 모든 트리의 크기를 K배만큼 키우기로 했다.

 그러나 크리스마스트리는 상대적으로 덜 전지전능해, 서로 다른 트리의 받침대끼리 겹쳐질 수 없다. 

잠시 겨울잠을 자러 간 GM요한을 대신해 정수 K의 최댓값을 구하여라. 

첫째 줄에 크리스마스트리의 개수 N이 주어진다.

둘째 줄부터 N개의 줄에 걸쳐, i+1번째 줄에 I번째 크리스마스트리의 좌표 Xi, Yi가 주어진다.

N+2번째 줄에 크리스마스트리의 받침대의 반지름 R_1, R_2, ..., R_N가 순서대로 주어진다.

입력값의 범위

2 <= N <= 1e5

1 <= R_i <= 1e3

1 <= Xi, Yi <= 1e6

채점데이터의 20%에 대해서, 2 <= N <=1000, R_i=1이다.

첫째 줄에 자연수 중에서 GM요한이 크리스마스트리들을 키울 수 있는 배율 K의 최댓값을 출력한다.