민원이 넘쳐흘러

DJ욱제는 자신의 디제잉을 사람들에게 알리기로 했다. 그래서 새벽 3시에 슈퍼카를 타고 아파트 단지를 돌아다니며 최고 볼륨으로 디제잉을 시작했다.

하지만 스피커 하나로는 예술의 경지에 다가갈 수 없었다. 그래서 DJ욱제는 광역 디제잉(광역딜)을 하기로 했다.

1. 아파트 단지는 2차원 격자로 표현되며, 두 점 $(x_1, y_1)$, $(x_2, y_2)$의 거리는 $|x_1 - x_2| + |y_1 - y_2|$이다.
2. DJ욱제는 $N$개의 스피커를 각 $(x_i, y_i)$ 위치에 설치했다.
3. 스피커마다 크기가 다르다. $i$번째 스피커의 크기가 $S_i$이고 볼륨이 $V$이면, 그 스피커의 음악은 스피커와의 거리가 $V \times S_i$ 이내인 모든 점에서 들을 수 있다.
4. 볼륨은 정수 단위로만 조절할 수 있으며, 모든 스피커의 볼륨은 같다.
5. 『 예술은 볼륨이다. 』

DJ욱제는 볼륨을 높이며 예술의 경지에 다다르고 있다! 하지만 예술을 모르는 사람들은 한 번에 두 개 이상의 스피커에서 음악이 들리면 민원을 넣는다고 한다. 그래서 DJ욱제는 민원이 들어오지 않는 범위에서 볼륨을 최대한 키우기로 했다. 소리가 들리는 범위의 경계선이나 경계점이 겹치는 경우는 음악이 겹치지 않는 것으로 본다.

DJ욱제의 예술(볼륨)을 온몸으로 느껴보자! DJ욱제의 예술(볼륨)은 얼마나 커질 수 있을까?

첫째 줄에 스피커 개수 $N$이 주어진다.

둘째 줄에 스피커의 크기 $S_1, S_2, \ldots, S_N$이 순서대로 주어진다.

셋째 줄부터 $N$개의 줄에 걸쳐, $i+2$번째 줄에 $i$번 스피커의 좌표 $x_i, y_i$가 주어진다. 중복되는 좌표는 없다.

주어지는 모든 입력은 1 이상의 정수이다.

DJ욱제가 다다를 수 있는 예술(볼륨)의 최대 크기를 출력한다.

• $2 \le N \le 100000$
• $1 \le S_i \le 1000$
• $1 \le x_i, y_i \le 1000000$