17423번 - 민원이 넘쳐흘러 서브태스크

🎵 DJ욱제는 슈퍼카 위에서 디제잉을 하고 있다. 🎵

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

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

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

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

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

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

둘째 줄에 스피커의 크기 S₁, S₂, ..., S_N가 순서대로 주어진다.

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

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

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

• 2 ≤ N ≤ 100,000
• 1 ≤ S_i ≤ 1,000
• 1 ≤ x_i, y_i ≤ 1,000,000

이 서브태스크는 다음의 조건을 만족한다.

• 2 ≤ N ≤ 1,000
• S_i = 1

이 서브태스크는 다음의 조건을 만족한다.

• 2 ≤ N ≤ 1,000

이 서브태스크는 추가 제한 조건이 없다.