시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
5 초 (언어별 추가 시간 없음) 512 MB 220 65 21 60.000%

문제

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

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

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

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

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

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

입력

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

둘째 줄에 스피커의 크기 S1S2, ..., SN가 순서대로 주어진다.

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

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

출력

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

제한

  • 2 ≤ N ≤ 100,000
  • 1 ≤ Si ≤ 1,000
  • 1 ≤ xi, yi ≤ 1,000,000

서브태스크 1 (23점)

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

  • 2 ≤ ≤ 1,000
  • Si = 1

서브태스크 2 (15점)

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

  • 2 ≤ ≤ 1,000

서브태스크 3 (62점)

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

예제 입력 1

4
2 1 1 3
2 2
1 7
6 6
5 13

예제 출력 1

2

본문의 그림에 대한 예제이다.

예제 입력 2

2
1 1
1 1
1000000 1000000

예제 출력 2

999999

채점

  • 예제는 채점하지 않는다.