human
Examples

Input

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

Output

6

Input



Output
Solve the task in PYTHON3.

=====
Give me a the Python code you requested?
assistant
#Here is the Python code you requested.

#!/usr/bin/env python3
# GRL_6_B: Minimum Cost Flow

WEIGHT_MAX = 10 ** 10

class Edge:
    __slots__ = ('src', 'dest', 'capacity', 'flow', 'cost')

    def __init__(self, v, w, capacity, cost=0):
        self.src = v
        self.dest = w
        self.capacity = capacity
        self.cost = cost
        self.flow = 0

    def other(self, v):
        if v == self.src:
            return self.dest
        else:
            return self.src

    def residual_capacity(self, v):
        if v == self.src:
            return self.capacity - self.flow
        else:
            return self.flow

    def cost_from(self, v):
        if v == self.src:
            return self.cost
        else:
            return -self.cost

    def add_flow(self, v, f):
        if v == self.src:
            self.flow += f
        else:
            self.flow -= f

    def __str__(self):
        return "{} {} {} {} {}".format(self.src, self.dest, self.capacity,
                                       self.cost, self.flow)

class Network:
    def __init__(self, v):
        self.v = v
        self._edges = [[] for _ in range(v)]

    def add(self, edge):
        self._edges[edge.src].append(edge)
        self._edges[edge.dest].append(edge)

    def adj(self, v):
        return self._edges[v]

    def flow(self, v):
        return sum(e.flow for e in self.adj(v) if e.src == v)

    def cost(self):
        cost = 0
        for v in range(self.v):
            for e in self.adj(v):
                if e.src == v:
                    cost += e.flow * e.cost
        return cost

    def __str__(self):
        s = ''
        for v in range(self.v):
            for e in self.adj(v):
                s += "{} {}\n".format(v, e)

        return s

def min_cost(network, s, t, f):
    def augment_path():
        def relax(edge, v):
            w = edge.other(v)
            c = edge.cost_from(v)
            if e.residual_capacity(v) > 0 and dists[w] > dists[v] + c:
                dists[w] = dists[v] + c
                edge_to[w] = e
               ...