import math
import numpy
import copy
import time

def schrage():
    mega_maszyna = []

    file_handle = open('data2.txt', 'r')

    lines_list = file_handle.readlines()

    zadania, maszyna = (int(val) for val in lines_list[0].split())

    mega_kursor = [0] * maszyna

    dane = [[int(val) for val in line.split()] for line in lines_list[1:]]

    for i in range(1, maszyna + 1):
        mini_maszyna = [0] * zadania

        j = i
        for i in range(0, zadania):
            mini_maszyna[i] = dane[i][j - 1]

        mega_maszyna.append(mini_maszyna)

    t = 0
    k = 0
    c_max = 0
    G = [];
    N = list(range(0, zadania))
    lista_pomocnicza = []
    pi = [0] * zadania
    r = mega_maszyna[0]
    p = mega_maszyna[1]
    q = mega_maszyna[2]

    rnowe = r[::]
    pnowe = p[::]
    qnowe = q[::]
    globals()['rnowe'] = rnowe
    globals()['pnowe'] = pnowe
    globals()['qnowe'] = qnowe

    # --------------------------DEFINICJE--------------------------#

    q_kopia = q[::]
    Q = []
    j = []
    while ((G != []) or (N != [])):

        while ((N != []) and (min(value for value in r if value != None) <= t)):
            e = min(value for value in r if value != None)
            e_arg = r.index(e)
            r[e_arg] = None

            G.append(e_arg)
            N.remove(e_arg)

            j.append(e_arg)

        for i in range(0, len(G)):
            x = q[G[i]]
            Q.append(x)


        if G == []:
            t = min(value for value in r if value != None)

        else:
            e = max(value for value in Q if value != None)

            eq = Q.index(e)
            e_arg = G[eq]

            q_kopia[e_arg] = None

            pi[k] = e_arg
            k = k + 1
            t = t + p[e_arg]
            c_max = max(c_max, t + q[e_arg])

            G.remove(e_arg)


        Q = []
        globals()['c_max'] = c_max
        globals()['pi'] = pi
        globals()['zadania'] = zadania
        globals()['j_arg'] = e_arg
        globals()['t'] = t
        globals()['j'] = j
        globals()['r'] = r
        globals()['p'] = p
        globals()['q'] = q

def schrage_przerwania():
    mega_maszyna = []

    file_handle = open('data2.txt', 'r')

    lines_list = file_handle.readlines()

    zadania, maszyna = (int(val) for val in lines_list[0].split())

    mega_kursor = [0] * maszyna

    dane = [[int(val) for val in line.split()] for line in lines_list[1:]]

    for i in range(1, maszyna + 1):
        mini_maszyna = [0] * zadania

        j = i
        for i in range(0, zadania):
            mini_maszyna[i] = dane[i][j - 1]

        mega_maszyna.append(mini_maszyna)

    t = 0
    k = 0
    c_max = 0
    G = [];
    N = list(range(0, zadania))
    lista_pomocnicza = []
    pi = [0] * zadania
    r = mega_maszyna[0]
    p = mega_maszyna[1]
    q = mega_maszyna[2]

    r_core = r[::]
    p_core = p[::]
    q_core = q[::]

    q[0] = math.inf
    l = 0

    # --------------------------DEFINICJE--------------------------#
    q_kopia = q[::]
    Q = []

    while ((G != []) or (N != [])):

        while ((N != []) and (min(value for value in r if value != None) <= t)):
            e = min(value for value in r if value != None)
            e_arg = r.index(e)

            G.append(e_arg)
            N.remove(e_arg)

            if q[e_arg] > q[l]:
                p[l] = t - r[e_arg]
                t = r[e_arg]
                if p[l] > 0:
                    G.append(l)

            r[e_arg] = None

            if q[0] == math.inf:
                q[0] = q_core[0]

        for i in range(0, len(G)):
            x = q[G[i]]
            Q.append(x)

        if G == []:
            t = min(value for value in r if value != None)

        else:
            e = max(value for value in Q if value != None)

            eq = Q.index(e)
            e_arg = G[eq]

            l = e_arg
            t = t + p[e_arg]
            c_max = max(c_max, t + q[e_arg])

            G.remove(e_arg)

        Q = []
        P = mega_maszyna[1]

        globals()['c_max'] = c_max
        globals()['pi'] = pi


# ---------------------  INICJALIZACJA  ---------------------

def Carlier():

    UB = 10000000

    # ---------------------------  1  ---------------------------

    schrage()
    U = c_max

    # ---------------------------  2  ---------------------------

    if U < UB:
        UB = U
        pi_nowe = pi[::]

    # ---------------------------  3  ---------------------------
    j = list(range(0, zadania))

    #print(j_arg)
    b = max(value for value in j if (c_max == t + q[j_arg]))

    #b = j_arg

    #print(b)

    a = min(value for value in j)

    #print(a)

    j = list(range(a, b))

    if (q[j_arg] < q[b]):
        c = max(value for value in j)
        #print(c)

    else:
        c = None
        #print(c)

    # ---------------------------  4  ---------------------------
    if c is None:
        return

    # ---------------------------  5  ---------------------------
    c = 0

    #print(c)

    granice = list(range(c+1, b+1))
    #print(granice)
    r_pomoc = []
    q_pomoc = []
    p_pomoc = []

    for i in range (c+1,b+1):

        r_pomoc.append(rnowe[i])
        q_pomoc.append(qnowe[i])
        p_pomoc.append(pnowe[i])

        #print(r_pomoc)
        #print(q_pomoc)
        #print(p_pomoc)

    er = min(r_pomoc)
    qu = min(q_pomoc)
    pe = sum(p_pomoc)

    print(er, qu, pe)
    # ---------------------------  6  ---------------------------
    r_new = rnowe[::]
    r_new[c] = max(rnowe[c],(er+pe))

    # ---------------------------  7  ---------------------------

    schrage_przerwania()
    LB = c_max

    # ---------------------------  8  ---------------------------

    if LB < UB:

    # ---------------------------  9  ---------------------------

        Carlier()

    # ---------------------------  10  ---------------------------

    r_new = rnowe[::]

    # ---------------------------  11  ---------------------------

    q_new = qnowe[::]
    q_new[c] = max(qnowe[c],(qu+pe))

    # ---------------------------  12  ---------------------------

    schrage_przerwania()
    LB = c_max

    # ---------------------------  13  ---------------------------

    if LB < UB:

    # ---------------------------  14  ---------------------------

        Carlier()

    # ---------------------------  15  ---------------------------

    q_new = qnowe[::]


Carlier()
#print("Cmax: ", UB)