민원이 넘쳐흘러
시간 제한5초메모리 제한512 MB
맨해튼 거리에서 경계 접촉은 겹침으로 치지 않을 때, 어떤 점도 두 스피커의 반경 V*Si 안에 동시에 들어가지 않는 최대 정수 볼륨 V를 구한다. 경계값을 이분 탐색하고 각 스피커 쌍의 허용 한계를 기하로 판정한다. 경계값 이분탐색과 쌍별 기하 판정이 핵심이다.
문제
🎵 DJ욱제는 슈퍼카 위에서 디제잉을 하고 있다. 🎵
DJ욱제는 자신의 엄청난 디제잉을 사람들에게 알리기로 했다. 그래서 새벽 3시에 슈퍼카를 타고 아파트 단지를 누비며 최고 볼륨으로 디제잉을 하기 시작했다. 😎
하지만 스피커 하나로는 예술의 경지에 다가갈 수 없었다. 그래서 DJ욱제는 다음과 같이 광역디제잉(광역딜)을 하기로 했다.
- 아파트 단지는 2차원 격자로 표현되며, 두 점 (x1, y1), (x2, y2)의 거리는 |x1 - x2| + |y1 - y2| 이다.
- DJ욱제는 N개의 스피커를 각 (xi, yi)에 설치했다.
- 스피커들은 크기가 제각각이다. i번째 스피커의 크기가 Si이고 볼륨이 V이면, 그 스피커의 음악은 스피커와의 거리가 V×Si 이내인 모든 점에서 들을 수 있다.
- 볼륨은 정수 단위로만 조작 가능하며, 모든 스피커의 볼륨은 같다.
- 『 예술은 볼륨이다. 』
DJ욱제는 볼륨을 높이며 예술의 경지에 다다르고 있다! 하지만 예술을 모르는 어떤 사람들은 한 번에 두 개 이상의 스피커에서 음악이 들리면 민원을 넣는다고 한다. (;;) 그래서 DJ욱제는 민원이 들어오지 않는 선에서 볼륨을 최대한으로 키우기로 했다. 소리가 들리는 범위의 경계선이나 경계점이 겹치는 경우는 음악이 겹치지 않는 걸로 치자.
DJ욱제의 예술(볼륨)을 온 몸으로 느껴보자! DJ욱제의 예술(볼륨)은 얼마나 커질 수 있을까?
입력
첫째 줄에 스피커 개수 N이 주어진다.
둘째 줄에 스피커의 크기 S1, S2, ..., SN가 순서대로 주어진다.
셋째 줄부터 N개의 줄에 걸쳐, i+2번째 줄에 i번 스피커의 좌표 xi, yi가 주어진다. 중복되는 좌표는 없다.
주어지는 모든 입력은 1 이상의 정수이다.
출력
DJ욱제가 다다를 수 있는 예술(볼륨)의 최대 크기를 출력한다.
제한
- 2 ≤ N ≤ 100,000
- 1 ≤ Si ≤ 1,000
- 1 ≤ xi, yi ≤ 1,000,000