Warehouse

The streets of New Byte City form a rectangular grid. The streets running east-west are called h-streets, and those running north-south are called v-streets. The v-streets are numbered from $1$ to $500{,}000{,}000$ from west to east, and the h-streets are numbered from $1$ to $500{,}000{,}000$ from south to north. Every v-street crosses every h-street, so a crossroads is written as a pair $(x, y)$ meaning the $x$-th v-street meets the $y$-th h-street. Consecutive v-streets, and consecutive h-streets, are exactly one kilometre apart.

There are $n$ shops in the city, each standing at a crossroads. A merchant supplies every shop from a single warehouse, which also stands at a crossroads. Each delivery is a separate course: the lorry leaves the warehouse, drives to one shop, and drives back, always taking a shortest route each way. The shop at $(x_i, y_i)$ receives $t_i$ deliveries per day.

A lorry may travel along the streets and diagonally across the blocks, so the length of a shortest route between crossroads $(x_i, y_i)$ and $(x_j, y_j)$ is the Chebyshev distance $\max(|x_i - x_j|,\ |y_i - y_j|)$ kilometres.

If the warehouse is built at crossroads $(x_m, y_m)$, the lorry's total daily driving distance is

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

where the factor $2$ counts the return leg of every course. Determine the smallest possible value of $D$ over all crossroads at which the warehouse could be built.

The first line contains one integer $n$ $(1 \le n \le 100{,}000)$, the number of shops.

Each of the next $n$ lines contains three integers $x_i$, $y_i$ and $t_i$ $(1 \le x_i, y_i \le 500{,}000{,}000,\ 1 \le t_i \le 1{,}000{,}000)$, separated by single spaces: the $i$-th shop stands at the crossing of the $x_i$-th v-street and the $y_i$-th h-street and receives $t_i$ deliveries per day.

Print one integer: the minimum possible total daily driving distance, that is $\min_{(x_m, y_m)} D(x_m, y_m)$ taken over every crossroads $(x_m, y_m)$.

In the first example the shops sit at $(2, 2)$, $(6, 2)$ and $(4, 6)$, each with one delivery per day. Building the warehouse at $(4, 4)$ makes the Chebyshev distance to every shop equal to $2$, so the total daily distance is $2 \cdot (2 + 2 + 2) = 12$, which is optimal.