창고

뉴바이트시의 도로는 직사각형 격자를 이룬다. 동서로 뻗은 도로를 가로도로, 남북으로 뻗은 도로를 세로도로라고 부른다. 세로도로는 서쪽에서 동쪽으로 $1$번부터 $500{,}000{,}000$번까지, 가로도로는 남쪽에서 북쪽으로 $1$번부터 $500{,}000{,}000$번까지 번호가 매겨져 있다. 모든 세로도로는 모든 가로도로와 교차하므로, 각 교차로는 "$x$번째 세로도로와 $y$번째 가로도로가 만나는 지점"이라는 뜻의 좌표 $(x, y)$로 나타낼 수 있다. 이웃한 두 세로도로 사이의 거리와 이웃한 두 가로도로 사이의 거리는 모두 정확히 $1$킬로미터이다.

도시에는 교차로마다 하나씩, 모두 $n$개의 상점이 있다. 상인은 하나의 창고에서 모든 상점에 물건을 공급하며, 창고 역시 어떤 교차로에 세워진다. 배송은 한 번에 한 상점씩 이루어진다. 트럭은 창고에서 출발해 한 상점까지 갔다가 다시 창고로 돌아오며, 갈 때와 올 때 모두 항상 최단 경로를 택한다. $(x_i, y_i)$에 있는 상점은 하루에 $t_i$번 배송을 받는다.

트럭은 도로를 따라서도, 블록을 대각선으로 가로질러서도 이동할 수 있으므로, 교차로 $(x_i, y_i)$와 $(x_j, y_j)$ 사이 최단 경로의 길이는 체비쇼프 거리 $\max(|x_i - x_j|,\ |y_i - y_j|)$ 킬로미터이다.

창고를 교차로 $(x_m, y_m)$에 세우면 트럭이 하루에 이동하는 총 거리는

$D(x_m, y_m) = 2 \sum_{i=1}^{n} t_i \cdot \max(|x_m - x_i|,\ |y_m - y_i|)$

이다. 여기서 계수 $2$는 매 배송마다 창고로 돌아오는 길을 포함하기 때문에 붙는다. 창고를 세울 수 있는 모든 교차로에 대하여 $D$의 최솟값을 구하여라.

첫째 줄에 상점의 개수 $n$ $(1 \le n \le 100{,}000)$이 주어진다.

다음 $n$개의 줄에는 각각 세 정수 $x_i$, $y_i$, $t_i$ $(1 \le x_i, y_i \le 500{,}000{,}000,\ 1 \le t_i \le 1{,}000{,}000)$가 공백 하나로 구분되어 주어진다. 이는 $i$번째 상점이 $x_i$번째 세로도로와 $y_i$번째 가로도로가 만나는 교차로에 있으며 하루에 $t_i$번 배송을 받는다는 뜻이다.

트럭이 하루에 이동하는 총 거리의 최솟값, 즉 모든 교차로 $(x_m, y_m)$에 대한 $\min_{(x_m, y_m)} D(x_m, y_m)$을 정수 하나로 출력한다.

첫 번째 예제에서 상점은 $(2, 2)$, $(6, 2)$, $(4, 6)$에 있으며 각각 하루에 한 번 배송을 받는다. 창고를 $(4, 4)$에 세우면 모든 상점까지의 체비쇼프 거리가 $2$가 되어, 하루 총 거리는 $2 \cdot (2 + 2 + 2) = 12$이고 이것이 최솟값이다.