AGC034D AC!!!

// LETS FUCKING GO

struct Edge {
    to: int,
    next: int,
    cap: int,
    cost: int
}

struct Queue {
	l: int[],
    r: int[],
    function push(self: Queue, x: int) { self.l.push(x); }
    function pop(self: Queue) -> int {
        if (self.r.length() > 0) {
            let x = self.r[self.r.length() - 1];
            self.r.pop();
            return x;
        }
        while (self.l.length() > 0) {
            let x = self.l[self.l.length() - 1];
            self.l.pop();
            self.r.push(x);
        }
        let x = self.r[self.r.length() - 1];
        self.r.pop();
        return x;
    }
    function empty(self: Queue) -> bool { return (self.l.length() + self.r.length()) == 0; }
}

function min(a: int, b: int) -> int {
    if (a < b) { return a; }
    return b;
}

function add_edge(by: int, to: int, cap: int, cost: int, edges: Edge[], head: int[], cur_edge: int[]) {
    cur_edge[0] += 1;
    edges[cur_edge[0]] = new Edge { to: to, next: head[by], cap: cap, cost: cost };
	head[by] = cur_edge[0];
}

function add(u: int, v: int, cap: int, cost: int, edges: Edge[], head: int[], cur_edge: int[]) {
	add_edge(u, v, cap, cost, edges, head, cur_edge);
    add_edge(v, u, 0, -cost, edges, head, cur_edge);
}

function spfa(n: int, s: int, t: int, pre: int[], vis: int[], c: int[], edges: Edge[], head: int[]) -> bool {
    for (let i = 1; i <= n; i += 1) { pre[i] = -1; vis[i] = 0; c[i] = 1000000000000000000; }
    let q = new Queue { l: [], r: [] };
	q.push(s);
    vis[s] = 1; c[s] = 0;
	while (!q.empty()) {
		let u = q.pop();
        vis[u] = 0;
		for (let i = head[u]; i > 0; i = edges[i].next) {
			let v = edges[i].to;
			if (edges[i].cap != 0 && c[v] > c[u] + edges[i].cost) {
				c[v] = c[u] + edges[i].cost;
				pre[v] = i;
                if (vis[v] == 0) {
                    vis[v] = 1;
                    q.push(v);
                }
			}
		}

    }
	return pre[t] != -1;
}

function mcmf(n: int, s: int, t: int, pre: int[], vis: int[], c: int[], edges: Edge[], head: int[]) -> int {
	let max_flow = 0;
	let min_cost = 0;
	while (spfa(n, s, t, pre, vis, c, edges, head)) {
		let x = t;
        let flow = 1000000000;
        while (x != s) { flow = min(flow, edges[pre[x]].cap); x = edges[pre[x] ^ 1].to; }
		max_flow += flow;
        x = t;
        min_cost += c[t] * flow;
		while (x != s) {
			edges[pre[x]].cap -= flow;
			edges[pre[x] ^ 1].cap += flow;
			x = edges[pre[x] ^ 1].to;
		}
    }
	return min_cost;
}

function solve(input: string) -> string {
    let z = input.split("\n");
    let n = int(z[0]);
    let rx: int[] = [0];
    let ry: int[] = [0];
    let rc: int[] = [0];
    for (let i = 1; i <= n; i += 1) {
        let ps = z[i].split(" ");
        rx.push(int(ps[0]));
        ry.push(int(ps[1]));
        rc.push(int(ps[2]));
    }
    let bx: int[] = [0];
    let by: int[] = [0];
    let bc: int[] = [0];
    for (let i = n + 1; i <= 2 * n; i += 1) {
        let ps = z[i].split(" ");
        bx.push(int(ps[0]));
        by.push(int(ps[1]));
        bc.push(int(ps[2]));
    }
    let maxn = 25000;
    let head: int[] = [];
    let vis: int[] = [];
    let pre: int[] = [];
    let c: int[] = [];
    let edges: Edge[] = [];
    for (let i = 0; i < maxn; i += 1) { head.push(0); }
    for (let i = 0; i < maxn; i += 1) { vis.push(0); }
    for (let i = 0; i < maxn; i += 1) { pre.push(0); }
    for (let i = 0; i < maxn; i += 1) { c.push(0); }
    for (let i = 0; i < maxn; i += 1) { edges.push(new Edge { to: -1, next: -1, cap: -1, cost: -1 }); }
    let cur_edge = [1];
	let tp1 = 2 * n + 1;
    let tp2 = 2 * n + 2;
    let tp3 = 2 * n + 3;
    let tp4 = 2 * n + 4;
    let s = 2 * n + 5;
    let t = 2 * n + 6;
    for (let i = 1; i <= n; i += 1) {
        add(s, i, rc[i], 0, edges, head, cur_edge);
        add(n + i, t, bc[i], 0, edges, head, cur_edge);
    }
    for (let i = 1; i <= n; i += 1) {
        add(i, tp1, rc[i], -(rx[i] + ry[i]), edges, head, cur_edge);
        add(i, tp2, rc[i], -(rx[i] - ry[i]), edges, head, cur_edge);
        add(i, tp3, rc[i], -(-rx[i] + ry[i]), edges, head, cur_edge);
        add(i, tp4, rc[i], -(-rx[i] - ry[i]), edges, head, cur_edge);
    }
    for (let i = 1; i <= n; i += 1) {
        add(tp1, n + i, bc[i], -(-bx[i] - by[i]), edges, head, cur_edge);
        add(tp2, n + i, bc[i], -(-bx[i] + by[i]), edges, head, cur_edge);
        add(tp3, n + i, bc[i], -(bx[i] - by[i]), edges, head, cur_edge);
        add(tp4, n + i, bc[i], -(bx[i] + by[i]), edges, head, cur_edge);
    }
    n = t;
    let ans = mcmf(n, s, t, pre, vis, c, edges, head);
    return string(-ans);
}