import math
def schrage():
    mega_maszyna = []

    file_handle = open('data.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]




    # --------------------------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)
            r[e_arg] = None

            G.append(e_arg)
            N.remove(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
def schrage_przerwania():

    mega_maszyna = []

    file_handle = open('data.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  ---------------------

UB = 0

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

schrage()
U = c_max

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