30973번 - Shoot! Take a Panorama

문제

진주 나들이를 온 보선이는 진주의 유명한 수목원인 경상남도수목원에 갔다. 이 수목원에는 스스로 빛을 내는 신비한 나무인 빛나무와 이들이 자라는 빛나무원이 있어서 관광객들에게 인기가 많다. 경상남도수목원에서는 관광객들을 위해 파노라마 포토 스팟이라는 특별한 지점을 정했는데, 이 지점에서 빛나무들을 파노라마로 찍으면 정말 예쁜 사진을 찍을 수 있다. 하지만 자기말고 아무도 믿지 못하는 보선이는 자기만의 파노라마 포토 스팟을 찾기로 하였다.

보선이는 자기만의 파노라마 포토 스팟을 찾기 위해 일단 경상남도수목원을 좌표평면으로 생각하기로 했다. 그리고 빛나무는 좌표평면 위의 점으로, 빛나무원은 좌표평면 위의 두 점 $(X_{min}, Y_{min}),ドル $(X_{max}, Y_{max})$을 꼭짓점으로 갖는 직사각형으로 생각하기로 했다. 빛나무원의 네 변은 각각 x축 또는 y축과 평행하다.

빛나무원에는 총 $N$그루의 빛나무가 있다. 모든 빛나무는 빛나무원의 안이나 경계에 위치해 있으며, 빛나무는 매우 얇아 같은 자리에 여러 그루가 심어져 있을 수 있다.

보선이는 x좌표와 y좌표가 모두 정수인 지점에서 모든 빛나무를 파노라마로 찍으려고 한다. 하지만 빛나무원의 안이나 경계에서는 사진을 찍을 수 없다. 또한, 보선이는 빛나무와의 거리가 멀수록 빛나무의 본래의 아름다움이 사진에 담기지 않아 불만족스럽다고 생각한다. 더 밝은 빛나무일수록 멀리서 찍었을 때 아쉬움이 크기 때문에, $i$번째 빛나무의 좌표와 밝기를 각각 $(X_i, Y_i),ドル $L_i$라 할 때, 점 $(X_c, Y_c)$에서 찍은 사진의 불만족도는 다음과 같이 표현될 수 있다.$$\sum_{i=1}^{N} \pmatrix{\left(\left(X_c - X_i\right)^2 + \left(Y_c - Y_i\right)^2\right) \times L_i}$$

보선이는 불만족도가 가장 낮은 사진을 찍을 수 있는 지점을 보선이만의 파노라마 포토 스팟으로 정할 것이다. 만약 그런 지점이 여럿이라면 그 중에서 아무 지점으로 정하기로 했다. 보선이만의 파노라마 포토 스팟에서 찍은 사진의 불만족도를 알아보자. 서로 다른 빛나무는 서로 내는 빛의 밝기에 영향을 주지 않으며, 여러 빛나무가 일직선 상에 있어도 가려서 비치지 않는 빛은 없다고 가정하자.

입력

첫 번째 줄에는 빛나무의 수 $N$이 주어진다.

두 번째 줄에는 빛나무원의 두 꼭짓점 $(X_{min}, Y_{min}),ドル $(X_{max}, Y_{max})$을 나타내는 $X_{min},ドル $Y_{min},ドル $X_{max},ドル $Y_{max}$가 공백으로 구분되어 주어진다.

세 번째 줄부터 N개의 줄에 걸쳐 $i$번째 빛나무의 정보 $X_i,ドル $Y_i,ドル $L_i$가 주어진다. 이는 $i$번째 빛나무의 좌표가 $(X_i, Y_i)$이며 밝기는 $L_i$라는 뜻이다.

입력으로 주어지는 모든 수는 정수이다.

출력

첫 번째 줄에 보선이만의 파노라마 포토 스팟에서 찍은 사진의 불만족도를 출력한다.

제한

• 1ドル ≤ N ≤ 50,000円$
• $-1,000円,000円 ≤ X_{min}, Y_{min}, X_{max}, Y_{max} ≤ 1,000円,000円$
• $X_{min} < X_{max}$
• $Y_{min} < Y_{max}$
• $X_{min} ≤ X_i ≤ X_{max}$
• $Y_{min} ≤ Y_i ≤ Y_{max}$
• 0ドル ≤ L_i ≤ 10$

힌트