사진을 찍자! 파노라마

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

보선이는 자기만의 파노라마 포토 스팟을 찾기 위해 경상남도수목원을 좌표평면으로 생각하기로 했다. 빛나무는 좌표평면 위의 점이고, 빛나무원은 두 점 $(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} \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}$가 공백으로 구분되어 주어진다.

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

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

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

• $1 \le N \le 50\,000$
• $-1\,000\,000 \le X_{min}, Y_{min}, X_{max}, Y_{max} \le 1\,000\,000$
• $X_{min} < X_{max}$
• $Y_{min} < Y_{max}$
• $X_{min} \le X_i \le X_{max}$
• $Y_{min} \le Y_i \le Y_{max}$
• $0 \le L_i \le 10$