题面翻译

在一个二维坐标系内，点 $(RX_i,RY_i)$ 上有 $RC_i$ 个红球，点 $(BX_i,BY_i)$ 上有 $BC_i$ 个蓝球，且保证 $\sum_{i=1}^{n}RC_i=\sum_{i=1}^{n}BC_i$。

现在要你将这些红球蓝球一一配对，配对的价值为两球所在点之间的曼哈顿距离，请你求出配对完它们的最大价值和。

样例 #1

样例输入 #1

2
0 0 1
3 2 1
2 2 1
5 0 1

样例输出 #1

8

样例 #2

样例输入 #2

3
0 0 1
2 2 1
0 0 2
1 1 1
1 1 1
3 3 2

样例输出 #2

16

样例 #3

样例输入 #3

10
582463373 690528069 8
621230322 318051944 4
356524296 974059503 6
372751381 111542460 9
392867214 581476334 6
606955458 513028121 5
882201596 791660614 9
250465517 91918758 3
618624774 406956634 6
426294747 736401096 5
974896051 888765942 5
726682138 336960821 3
715144179 82444709 6
599055841 501257806 6
390484433 962747856 4
912334580 219343832 8
570458984 648862300 6
638017635 572157978 10
435958984 585073520 7
445612658 234265014 6

样例输出 #3

45152033546

提示

制約

• $1\ \leq\ N\ \leq\ 1000$
• $0\ \leq\ RX_i,RY_i,BX_i,BY_i\ \leq\ 10^9$
• $1\ \leq\ RC_i,BC_i\ \leq\ 10$
• $\sum_{i=1}^{N}\ RC_i\ =\ \sum_{i=1}^{N}\ BC_i$