题目描述

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

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

输入格式

第一行一个整数 $n$，表示点的个数。

接下来 $n$ 行，一行三个整数 $RX_i,RY_i,RC_i$。

接下来 $n$ 行，一行三个整数 $BX_i,BY_i,BC_i$。

输出格式

输出一个整数，表示最大价值和。

样例

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

8

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

16

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

45152033546

数据范围

对于全部数据，$1\le n\le 10$，$0\le RX_i,RY_i,BX_i,BY_i\le 10^9$，$1\le RC_i,BC_i\le 10$，$\sum RC_i=\sum BC_i$。