p03020 AtCoder Grand Contest 034 - Manhattan Max Matching
Snuke is playing with red and blue balls, placing them on a two-dimensional plane.

First, he performed N operations to place red balls. In the i-th of these operations, he placed RC_i red balls at coordinates (RX_i,RY_i). Then, he performed another N operations to place blue balls. In the i-th of these operations, he placed BC_i blue balls at coordinates (BX_i,BY_i). The total number of red balls placed and the total number of blue balls placed are equal, that is, \sum_{i=1}^{N} RC_i = \sum_{i=1}^{N} BC_i. Let this value be S.

Snuke will now form S pairs of red and blue balls so that every ball belongs to exactly one pair. Let us define the score of a pair of a red ball at coordinates (rx, ry) and a blue ball at coordinates (bx, by) as |rx-bx| + |ry-by|.

Snuke wants to maximize the sum of the scores of the pairs. Help him by finding the maximum possible sum of the scores of the pairs.

Constraints

* 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
* All values in input are integers.

Input

Input is given from Standard Input in the following format:


N
RX_1 RY_1 RC_1
RX_2 RY_2 RC_2
\vdots
RX_N RY_N RC_N
BX_1 BY_1 BC_1
BX_2 BY_2 BC_2
\vdots
BX_N BY_N BC_N


Output

Print the maximum possible sum of the scores of the pairs.

Examples

Input

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


Output

8


Input

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


Output

16


Input

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


Output

45152033546
```python
import sys
from collections import deque


def min_cost_flow(links, links_from, s, t, flow, n2):
    remain = flow
    result = 0
    INF = 10 ** 12
    predecessors = [0] * n2  # link_id

    while remain:
        # print(remain)
        distances = [INF] * n2
        updated = [False] * n2
        distances[s] = 0
        updated[s] = True
        q = deque([s])
        while q:
            v = q.popleft()
            vc = distances[v]
            updated[v] = False

            for li in links_from[v]:
                _, u, cap, cost = links[li]
                if cap == 0:
                    continue
                new_cost = vc + cost
                if new_cost >= distances[u]:
                    continue
                distances[u] = new_cost
                predecessors[u] = li
                if not updated[u]:
                    updated[u] = True
                    q.append(u)

        min_cap = remain
        v = t
        while v != s:
            li = predecessors[v]
            l = links[li]
            min_cap = min(min_cap, l[2])
            v = l[0]
        v = t
        while v != s:
            li = predecessors[v]
            l = links[li]
            l[2] -= min_cap
            links[li ^ 1][2] += min_cap
            v = l[0]
        remain -= min_cap
        result -= min_cap * distances[t]
    return result


n = int(input())
lines = sys.stdin.readlines()
n2 = 2 * n + 6
s, t = 0, 2 * n + 1
k1, k2, k3, k4 = range(n2 - 4, n2)
balls = 0
links_from = [[] for _ in range(n2)]
links = []  # [[src, tgt, capacity, unit_cost], ]


def add_link(s, t, cap, cost):
    i = len(links)
    links.append([s, t, cap, cost])
    links.append([t, s, 0, -cost])
    links_from[s].append(i)
    links_from[t].append(i + 1)


for i in range(n):
    ri = i + 1
    rx, ry, rc = map(int, lines[i].split())
    balls += rc
    add_link(s, ri, rc, 0)
    add_link(ri, k1, rc, rx + ry)
    add_link(ri, k2, rc, -rx + ry)
    add_link(ri, k3, rc, rx - ry)
    add_link(ri, k4, rc, -rx - ry)

for i in range(n, 2 * n):
    bi = i + 1
    bx, by, bc = map(int, lines[i].split())
    add_link(bi, t, bc, 0)
    add_link(k1, bi, bc, -bx - by)
    add_link(k2, bi, bc, bx - by)
    add_link(k3, bi, bc, -bx + by)
    add_link(k4, bi, bc, bx + by)

print(min_cost_flow(links, links_from, s, t, balls, n2))

```