#P18137. Waterfall Matrix

Waterfall Matrix

Waterfall Matrix

称一个 n×nn\times n 整数矩阵为 Waterfall Matrix,若每个元素都不小于其右侧和下方的相邻元素。

例如,下面就是一个 Waterfall Matrix:

Waterfall Matrix 示例

给定 nn 个互不重复的格子 (ai,bi)(a_i,b_i) 及期望值 cic_i。选择一个 Waterfall Matrix MM,最小化

∑i=1n∣Mai,bi−ci∣.\sum_{i=1}^n |M_{a_i,b_i}-c_i|.

输入格式

第一行包含 nn(1≤n≤2000001\le n\le200000)。

接下来 nn 行,每行包含 ai,bi,cia_i,b_i,c_i,满足 1≤ai,bi≤n1\le a_i,b_i\le n、1≤ci≤1091\le c_i\le10^9,且坐标互不相同。

输出格式

输出最小总代价。

样例

5
1 3 5
3 2 1
3 3 3
4 4 1
3 5 4
3