23826번 - 와이파이

가까운 소학습실까지도 나가기 싫어하는 우석이는 방에서 WiFi를 사용하고 싶어한다. 기본적으로 소학습실에도 공용 WiFi가 제공되어 있지만, 소학습실의 WiFi 속도에 만족하지 못한 학생들은 핫스팟 WiFi를 사용했고, 이 WiFi 전파가 소학습실의 WiFi 전파를 방해했다. 방해 전파에도 불구하고, 우석이는 사용할 수 있는 공용 WiFi 속도를 가늠하고 싶어 한다.

방은 $1$번부터 $N$번까지 총 $N$ 개가 있으며, 각 방과 소학습실의 위치는 2차원 평면 위의 한 점으로 표현할 수 있다. $i$번 방의 위치는 $(x_i, y_i)$이며, 소학습실의 위치는 $(x_0, y_0)$이다.

각 방에 도달하는 소학습실의 WiFi 속도를 계산하는 방법은 다음과 같다.

• 소학습실에는 에너지가 $E_0$인 공용 WiFi가 켜져 있다.
• $i$번 방에는 핫스팟 WiFi가 최대 1개 켜져 있다.
  • $E_i \neq 0$이면, 에너지가 $E_i$인 핫스팟 WiFi가 켜져 있고, $E_i = 0$이면 핫스팟 WiFi가 켜져있지 않다.
• 와이파이의 세기는, 와이파이의 에너지에서 WiFi가 켜진 곳과 WiFi를 사용하는 곳의 택시거리만큼 감쇠되며, $0$ 미만으로 감쇠되지는 않는다.
  • 즉, 에너지가 $P$이고 $(a, b)$에서 켜진 WiFi가 $(c, d)$에 도달할 때 WiFi의 세기는 $\max(0, P-(|a-c|+|b-d|))$이다.
• $i$번 방에 도달하는 와이파이의 속도는 $i$번 방에 도달한 공용 WiFi의 세기에서 $i$번 방에 도달한 모든 핫스팟 WiFi의 세기 합을 뺀 값으로 계산된다.
  • 와이파이의 속도가 $0$ 이하일 경우 $i$번 방에서 와이파이에 연결할 수 없다.

대담한 우석이는 와이파이를 위해서라면 다른 방에도 침입할 수 있다. 우석이를 위해 가장 공용 WiFi가 빠른 방의 공용 WiFi 속도를 구해주자.

첫 번째 줄에 방의 수 $N$이 공백으로 구분되어 주어진다.

다음 $N+1$ 개의 줄의 $i$ 번째 줄에는$x_{i-1}$, $y_{i-1}$, $E_{i-1}$가 공백으로 구분되어 주어진다.

가장 공용 WiFi 속도가 빠른 방에서의 속도를 공백을 두고 출력한다. 만약 모든 방에서 공용 WiFi에 연결할 수 없다면 “IMPOSSIBLE” (따옴표 제외) 을 출력한다.

• $1 \le N \le 1\, 000$
• $0 \le x_i, y_i \le 1\, 000$ ($0 \le i \le N$)
• $0 \le E_i \le 1\, 000$ ($1 \le i \le N$)
• $1\le E_0 \le 1\, 000\, 000$
• 입력으로 주어지는 모든 수는 정수이다.

같은 방이라도 핫스팟 WiFi가 켜져 있으면, 공용 WiFi 전파를 방해하는 것에 유의하여라.