Buggy python submission (verdict: Time Limit Exceeded):
# Dijkstra's algorithm with Priority Heap and Potential

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    H = [0] * N_
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = [s]
        updated = [False] * N_
        updated[s] = True

        while que :
            v = heappop(que)
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w] :
                    dist[w] = dist[v] + cost + H[v] - H[w]
                    pre_v[w], pre_e[w] = v, i
                    heappush(que, w)
                    updated[w] = True

        for i in range(N_) :
            H[i] += dist[i]

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * H[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
# Dijkstra's algorithm with Priority Heap and Potential

import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    H = [0] * N_
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = [0]
        updated = [False] * N_

        while que :
            v = heappop(que)
            updated[v] = False
            if updated[v] :
                continue

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w] :
                    dist[w] = dist[v] + cost + H[v] - H[w]
                    pre_v[w], pre_e[w] = v, i
                    heappush(que, w)
                    updated[w] = True

        for i in range(N_) :
            H[i] += dist[i]

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * H[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    H = [0] * N_
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = [(0, s)]

        while que :
            c, v = heappop(que)
            if dist[v] < c :
                continue

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w] :
                    dist[w] = dist[v] + cost + H[v] - H[w]
                    pre_v[w], pre_e[w] = v, i
                    heappush(que, (dist[w], w))

        for i in range(N_) :
            H[i] += dist[i]

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * H[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    H = [0] * N_
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = [(0, s)]

        while que :
            c, v = heappop(que)
            if dist[v] < c :
                continue

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 :
                    r = dist[v] + cost + H[v] - H[w]
                    if r < dist[w] :
                        dist[w] = r
                        pre_v[w], pre_e[w] = v, i
                        heappush(que, (r, w))

        for i in range(N_) :
            H[i] += dist[i]

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * H[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(N) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i + 1, Rc, 0)

    add_edge(i + 1, N1, INF, -(Rx + Ry))
    add_edge(i + 1, N2, INF, -(-Rx + Ry))
    add_edge(i + 1, N3, INF, -(Rx - Ry))
    add_edge(i + 1, N4, INF, -(-Rx - Ry))
    S += Rc

for i in range(N) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i + N5, INF, -(-Bx - By))
    add_edge(N2, i + N5, INF, -(Bx - By))
    add_edge(N3, i + N5, INF, -(-Bx + By))
    add_edge(N4, i + N5, INF, -(Bx + By))

    add_edge(i + N5, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    H = [0] * N_
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = [(0, s)]

        while que :
            c, v = heappop(que)
            if dist[v] < c :
                continue
            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w] :
                    dist[w] = r = dist[v] + cost + H[v] - H[w]
                    pre_v[w], pre_e[w] = v, i
                    heappush(que, (r, w))

        for i in range(N_) :
            H[i] += dist[i]

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * H[t]
        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(N) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i + 1, Rc, 0)

    add_edge(i + 1, N1, INF, -(Rx + Ry))
    add_edge(i + 1, N2, INF, -(-Rx + Ry))
    add_edge(i + 1, N3, INF, -(Rx - Ry))
    add_edge(i + 1, N4, INF, -(-Rx - Ry))
    S += Rc

for i in range(N) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i + N5, INF, -(-Bx - By))
    add_edge(N2, i + N5, INF, -(Bx - By))
    add_edge(N3, i + N5, INF, -(-Bx + By))
    add_edge(N4, i + N5, INF, -(Bx + By))

    add_edge(i + N5, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = [(0, s)]

        while que :
            c, v = heappop(que)
            if dist[v] < c :
                continue
            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = r = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    heappush(que, (r, w))

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]
        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(N) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i + 1, Rc, 0)

    add_edge(i + 1, N1, INF, -(Rx + Ry))
    add_edge(i + 1, N2, INF, -(-Rx + Ry))
    add_edge(i + 1, N3, INF, -(Rx - Ry))
    add_edge(i + 1, N4, INF, -(-Rx - Ry))
    S += Rc

for i in range(N) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i + N5, INF, -(-Bx - By))
    add_edge(N2, i + N5, INF, -(Bx - By))
    add_edge(N3, i + N5, INF, -(-Bx + By))
    add_edge(N4, i + N5, INF, -(Bx + By))

    add_edge(i + N5, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [float('inf')] * N_
        dist[s] = 0
        que = [(0, s)]

        while que :
            c, v = heappop(que)
            if dist[v] < c :
                continue
            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = r = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    heappush(que, (r, w))

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]
        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(N) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i + 1, Rc, 0)

    add_edge(i + 1, N1, float('inf'), -(Rx + Ry))
    add_edge(i + 1, N2, float('inf'), -(-Rx + Ry))
    add_edge(i + 1, N3, float('inf'), -(Rx - Ry))
    add_edge(i + 1, N4, float('inf'), -(-Rx - Ry))
    S += Rc

for i in range(N) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i + N5, float('inf'), -(-Bx - By))
    add_edge(N2, i + N5, float('inf'), -(Bx - By))
    add_edge(N3, i + N5, float('inf'), -(-Bx + By))
    add_edge(N4, i + N5, float('inf'), -(Bx + By))

    add_edge(i + N5, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))


Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [float('inf')] * N_
        dist[s] = 0
        update = True

        while update :
            update = False
            for v in range(N_) :
                if dist[v] == float('inf') :
                    continue
                
                for i, (to, cap, cost, _) in enumerate(G[v]) :
                    if cap > 0 and dist[to] > dist[v] + cost :
                        dist[to] = dist[v] + cost
                        pre_v[to] = v
                        pre_e[to] = i
                        update = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(N) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i + 1, Rc, 0)

    add_edge(i + 1, N1, float('inf'), -(Rx + Ry))
    add_edge(i + 1, N2, float('inf'), -(-Rx + Ry))
    add_edge(i + 1, N3, float('inf'), -(Rx - Ry))
    add_edge(i + 1, N4, float('inf'), -(-Rx - Ry))
    S += Rc

for i in range(N) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i + N5, float('inf'), -(-Bx - By))
    add_edge(N2, i + N5, float('inf'), -(Bx - By))
    add_edge(N3, i + N5, float('inf'), -(-Bx + By))
    add_edge(N4, i + N5, float('inf'), -(Bx + By))

    add_edge(i + N5, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    H = [0] * N_
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [float('inf')] * N_
        dist[s] = 0
        que = [(0, s)]

        while que :
            c, v = heappop(que)
            if dist[v] < c :
                continue
            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w] :
                    dist[w] = r = dist[v] + cost + H[v] - H[w]
                    pre_v[w], pre_e[w] = v, i
                    heappush(que, (r, w))
        
        # if dist[t] == float('inf') :
        #     return -1

        for i in range(N_) :
            H[i] += dist[i]

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * H[t]
        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(N) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i + 1, Rc, 0)

    add_edge(i + 1, N1, float('inf'), -(Rx + Ry))
    add_edge(i + 1, N2, float('inf'), -(-Rx + Ry))
    add_edge(i + 1, N3, float('inf'), -(Rx - Ry))
    add_edge(i + 1, N4, float('inf'), -(-Rx - Ry))
    S += Rc

for i in range(N) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i + N5, float('inf'), -(-Bx - By))
    add_edge(N2, i + N5, float('inf'), -(Bx - By))
    add_edge(N3, i + N5, float('inf'), -(-Bx + By))
    add_edge(N4, i + N5, float('inf'), -(Bx + By))

    add_edge(i + N5, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))


Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    H = [0] * N_
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [float('inf')] * N_
        dist[s] = 0
        que = [(0, s)]

        while que :
            c, v = heappop(que)
            if dist[v] < c :
                continue
            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w] :
                    dist[w] = r = dist[v] + cost + H[v] - H[w]
                    pre_v[w], pre_e[w] = v, i
                    heappush(que, (r, w))
        
        if dist[t] == float('inf') :
            return -1

        for i in range(N_) :
            H[i] += dist[i]

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * H[t]
        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(N) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i + 1, Rc, 0)

    add_edge(i + 1, N1, float('inf'), -(Rx + Ry))
    add_edge(i + 1, N2, float('inf'), -(-Rx + Ry))
    add_edge(i + 1, N3, float('inf'), -(Rx - Ry))
    add_edge(i + 1, N4, float('inf'), -(-Rx - Ry))
    S += Rc

for i in range(N) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i + N5, float('inf'), -(-Bx - By))
    add_edge(N2, i + N5, float('inf'), -(Bx - By))
    add_edge(N3, i + N5, float('inf'), -(-Bx + By))
    add_edge(N4, i + N5, float('inf'), -(Bx + By))

    add_edge(i + N5, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))


Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
import sys
from heapq import heappush, heappop

input = sys.stdin.readline

N = int(input())
R = [[int(i) for i in input().split()] for _ in range(N)]
B = [[int(i) for i in input().split()] for _ in range(N)]

class MinCostFlow :
    def __init__(self, N) :
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost) :
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

    def flow(self, s, t, f) :
        N, G = self.N, self.G

        ret = 0
        H = [0] * N
        pre_v = [0] * N
        pre_e = [0] * N

        while f :
            dist = [float('inf')] * N
            dist[s] = 0
            que = [(0, s)]

            while que :
                c, v = heappop(que)
                if dist[v] < c :
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]) :
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w] :
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        pre_v[w], pre_e[w] = v, i
                        heappush(que, (r, w))
            
            if dist[t] == float('inf') :
                return -1

            for i in range(N) :
                H[i] += dist[i]

            d, v = f, t
            while v != s :
                d = min(d, G[pre_v[v]][pre_e[v]][1])
                v = pre_v[v]

            f -= d
            ret += d * H[t]
            v = t
            while v != s :
                e = G[pre_v[v]][pre_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = pre_v[v]
        
        return ret

MCF = MinCostFlow(2 * N + 6)
f = 0
for i in range(N) :
    Rx, Ry, Rc = R[i]
    Bx, By, Bc = B[i]

    MCF.add_edge(0, i + 1, Rc, 0)

    MCF.add_edge(i + 1, N + 1, float('inf'), -(Rx + Ry))
    MCF.add_edge(i + 1, N + 2, float('inf'), -(-Rx + Ry))
    MCF.add_edge(i + 1, N + 3, float('inf'), -(Rx - Ry))
    MCF.add_edge(i + 1, N + 4, float('inf'), -(-Rx - Ry))

    MCF.add_edge(N + 1, i + N + 5, float('inf'), -(-Bx - By))
    MCF.add_edge(N + 2, i + N + 5, float('inf'), -(Bx - By))
    MCF.add_edge(N + 3, i + N + 5, float('inf'), -(-Bx + By))
    MCF.add_edge(N + 4, i + N + 5, float('inf'), -(Bx + By))

    MCF.add_edge(i + N + 5, 2 * N + 5, Bc, 0)

    f += Rc

print(-MCF.flow(0, 2 * N + 5, f))


Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))

Buggy python submission (verdict: Time Limit Exceeded):
from heapq import heappush, heappop

N = int(input())
R = [[int(i) for i in input().split()] for _ in range(N)]
B = [[int(i) for i in input().split()] for _ in range(N)]

class MinCostFlow :
    def __init__(self, N) :
        self.N = N
        self.G = [[] for i in range(N)]

    def add_edge(self, fr, to, cap, cost) :
        G = self.G
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

    def flow(self, s, t, f) :
        N, G = self.N, self.G

        ret = 0
        H = [0] * N
        pre_v = [0] * N
        pre_e = [0] * N

        while f :
            dist = [float('inf')] * N
            dist[s] = 0
            que = [(0, s)]

            while que :
                c, v = heappop(que)
                if dist[v] < c :
                    continue
                for i, (w, cap, cost, _) in enumerate(G[v]) :
                    if cap > 0 and dist[w] > dist[v] + cost + H[v] - H[w] :
                        dist[w] = r = dist[v] + cost + H[v] - H[w]
                        pre_v[w], pre_e[w] = v, i
                        heappush(que, (r, w))
            
            if dist[t] == float('inf') :
                return -1

            for i in range(N) :
                H[i] += dist[i]

            d, v = f, t
            while v != s :
                d = min(d, G[pre_v[v]][pre_e[v]][1])
                v = pre_v[v]

            f -= d
            ret += d * H[t]
            v = t
            while v != s :
                e = G[pre_v[v]][pre_e[v]]
                e[1] -= d
                G[v][e[3]][1] += d
                v = pre_v[v]
        
        return ret

MCF = MinCostFlow(2 * N + 6)
f = 0
for i in range(N) :
    Rx, Ry, Rc = R[i]
    Bx, By, Bc = B[i]

    MCF.add_edge(0, i + 1, Rc, 0)

    MCF.add_edge(i + 1, N + 1, float('inf'), -(Rx + Ry))
    MCF.add_edge(i + 1, N + 2, float('inf'), -(-Rx + Ry))
    MCF.add_edge(i + 1, N + 3, float('inf'), -(Rx - Ry))
    MCF.add_edge(i + 1, N + 4, float('inf'), -(-Rx - Ry))

    MCF.add_edge(N + 1, i + N + 5, float('inf'), -(-Bx - By))
    MCF.add_edge(N + 2, i + N + 5, float('inf'), -(Bx - By))
    MCF.add_edge(N + 3, i + N + 5, float('inf'), -(-Bx + By))
    MCF.add_edge(N + 4, i + N + 5, float('inf'), -(Bx + By))

    MCF.add_edge(i + N + 5, 2 * N + 5, Bc, 0)

    f += Rc

print(-MCF.flow(0, 2 * N + 5, f))

Fixed submission:
import sys
from collections import deque

input = sys.stdin.readline

N = int(input())
N_ = 2 * N + 6
N1, N2, N3, N4, N5 = range(N + 1, N + 6)
G = [[] for i in range(2 * N + 6)]
INF = 10 ** 12

def add_edge(fr, to, cap, cost) :
        G[fr].append([to, cap, cost, len(G[to])])
        G[to].append([fr, 0, -cost, len(G[fr]) - 1])

def flow(s, t, f) :
    ret = 0
    pre_v = [0] * N_
    pre_e = [0] * N_

    while f :
        dist = [INF] * N_
        dist[s] = 0
        que = deque([s])
        updated = [False] * N_
        updated[s] = True

        while que :
            v = que.popleft()
            if not updated[v] :
                continue

            updated[v] = False

            for i, (w, cap, cost, _) in enumerate(G[v]) :
                if cap > 0 and dist[w] > dist[v] + cost:
                    dist[w] = dist[v] + cost
                    pre_v[w], pre_e[w] = v, i
                    que.append(w)
                    updated[w] = True

        d, v = f, t
        while v != s :
            d = min(d, G[pre_v[v]][pre_e[v]][1])
            v = pre_v[v]

        f -= d
        ret += d * dist[t]

        v = t
        while v != s :
            e = G[pre_v[v]][pre_e[v]]
            e[1] -= d
            G[v][e[3]][1] += d
            v = pre_v[v]
    
    return ret

S = 0
for i in range(1, N + 1) :
    Rx, Ry, Rc = map(int, input().split())

    add_edge(0, i, Rc, 0)

    add_edge(i, N1, INF, -Rx - Ry)
    add_edge(i, N2, INF, Rx - Ry)
    add_edge(i, N3, INF, -Rx + Ry)
    add_edge(i, N4, INF, Rx + Ry)
    S += Rc

for i in range(N5, N_ - 1) :
    Bx, By, Bc = map(int, input().split())
    add_edge(N1, i, INF, Bx + By)
    add_edge(N2, i, INF, -Bx + By)
    add_edge(N3, i, INF, Bx - By)
    add_edge(N4, i, INF, -Bx - By)

    add_edge(i, N_ - 1, Bc, 0)

print(-flow(0, N_ - 1, S))