A well-known art union called "Kalevich is Alive!" manufactures objects d'art (pictures). The union consists of n painters who decided to organize their work as follows.

Each painter uses only the color that was assigned to him. The colors are distinct for all painters. Let's assume that the first painter uses color 1, the second one uses color 2, and so on. Each picture will contain all these n colors. Adding the j-th color to the i-th picture takes the j-th painter t_{ij} units of time.

Order is important everywhere, so the painters' work is ordered by the following rules:  Each picture is first painted by the first painter, then by the second one, and so on. That is, after the j-th painter finishes working on the picture, it must go to the (j + 1)-th painter (if j < n);  each painter works on the pictures in some order: first, he paints the first picture, then he paints the second picture and so on;  each painter can simultaneously work on at most one picture. However, the painters don't need any time to have a rest;  as soon as the j-th painter finishes his part of working on the picture, the picture immediately becomes available to the next painter. 

Given that the painters start working at time 0, find for each picture the time when it is ready for sale.


-----Input-----

The first line of the input contains integers m, n (1 ≤ m ≤ 50000, 1 ≤ n ≤ 5), where m is the number of pictures and n is the number of painters. Then follow the descriptions of the pictures, one per line. Each line contains n integers t_{i}1, t_{i}2, ..., t_{in} (1 ≤ t_{ij} ≤ 1000), where t_{ij} is the time the j-th painter needs to work on the i-th picture.


-----Output-----

Print the sequence of m integers r_1, r_2, ..., r_{m}, where r_{i} is the moment when the n-th painter stopped working on the i-th picture.


-----Examples-----
Input
5 1
1
2
3
4
5

Output
1 3 6 10 15 
Input
4 2
2 5
3 1
5 3
10 1

Output
7 8 13 21

Difficulty: interview

Starter code:

Solutions:
"""
Codeforces Round 241 Div 1 Problem B

Author  : chaotic_iak
Language: Python 3.3.4
"""

class InputHandlerObject(object):
    inputs = []

    def getInput(self, n = 0):
        res = ""
        inputs = self.inputs
        if not inputs: inputs.extend(input().split(" "))
        if n == 0:
            res = inputs[:]
            inputs[:] = []
        while n > len(inputs):
            inputs.extend(input().split(" "))
        if n > 0:
            res = inputs[:n]
            inputs[:n] = []
        return res
InputHandler = InputHandlerObject()
g = InputHandler.getInput

############################## SOLUTION ##############################
m,n = [int(x) for x in g()]
q = []
for i in range(m):
    q.append([int(x) for x in g()])
p = q[:]
for j in range(n):
    for i in range(m):
        if i == 0 and j == 0:
            continue
        if i == 0:
            p[i][j] = p[i][j-1] + q[i][j]
            continue
        if j == 0:
            p[i][j] = p[i-1][j] + q[i][j]
            continue
        p[i][j] = max(p[i-1][j], p[i][j-1]) + q[i][j]
for i in range(m):
    print(p[i][n-1], end=" ")


m,n = map(int,input().split())
shed = []
for i in range(m):
    shed.append(list(map(int,input().split())))
time = [0] * 51
ans = []
for i in range(m):
    tt = 0
    for j in range(n):
        tt = max(tt, time[j])+ shed[i][j]
        time[j] = tt
    ans.append(tt)
print(*ans)

m, n = (int(i) for i in input().split(' '))
time = [None] * m
for i in range(m):
    time[i] = list(int(i) for i in input().split(' '))
r = [0] * m
r[0] = time[0][0]
for i in range(1, m):
    r[i] = r[i - 1] + time[i][0]
for i in range(1,n):
    r[0] += time[0][i]
    for j in range(1,m):
        r[j] = time[j][i] + max(r[j-1],r[j])
print(' '.join(str(i) for i in r))


m,n=map(int,input().split())
s=[0]*n
for i in range(m):
    a=list(map(int,input().split()))
    s[0]=s[0]+a[0]
    for j in range(1,n):
        s[j]=max(s[j-1],s[j])+a[j]
    print(s[-1],end=' ')


#!/usr/bin/env python3
# -*- coding: utf-8 -*-

(M,N) = map(int, input().split())

times = []
for m in range(M):
    times.append( list( map(int, input().split())) )

man = [0] * N

time = 0
for m in range(M):
    for n in range(N):
        if n == 0:
            time = man[n] + times[m][n]
        else:
            time = max( time, man[n] ) + times[m][n]
        man[n] = time
    print (time, end=' ')
    # print("man = ", man)
    
print()



m, n = list(map(int, input().split()))
time_table = []

time_table.append([0] * n)
for _ in range(m):
    time_table.append(list(map(int, input().split())))

time_table = list(list(t) for t in zip(*time_table))
time_table.insert(0, [0] * (m + 1))

for i in range(1, len(time_table)):
    for j in range(1, len(time_table[i])):
        time_table[i][j] = max(time_table[i-1][j], time_table[i][j-1]) + time_table[i][j]

print(' '.join(str(i) for i in time_table[n][1:]))

n, m = map(int, input().split())
t = [0 for i in range(m)]
for i in range(n):
    c = list(map(int, input().split()))
    t[0] += c[0]
    for j in range(1, m):
        t[j] = max(t[j], t[j - 1]) + c[j]
    print(t[m - 1], end = ' ')

m, n = map(int, input().split())
t = []
for i in range(m):
  t += [list(map(int, input().split()))]
d = [0] * m
for i in range(n):
  d[0] += t[0][i]
  for j in range(1, m):
    d[j] = max(d[j - 1], d[j]) + t[j][i]
print(*d)

import sys
m,n=list(map(int,sys.stdin.readline().split()))
T=[]
for i in range(m):
    T.append(list(map(int,sys.stdin.readline().split())))
C=[0]*n
Ans=""
for i in range(m):
##    print(C)
##    print(T[i])
    t=C[0]
    for j in range(n):
        if(t<C[j]):
            t=C[j]+T[i][j]
        else:
            t+=T[i][j]
        C[j]=t
    Ans+=str(t)+" "
sys.stdout.write(Ans)
        


n, m = map(int, input().split())
t = [list(map(int, input().split())) for i in range(n)]
for j in range(m - 1): t[0][j + 1] += t[0][j]
for i in range(n - 1):
    t[i + 1][0] += t[i][0]
    for j in range(m - 1): t[i + 1][j + 1] += max(t[i + 1][j], t[i][j + 1])
print(' '.join(map(str, [p[m - 1] for p in t])))

m,n=map(int,input().split())
s=[0]*n
for i in range(m):
    a=list(map(int,input().split()))
    s[0]=s[0]+a[0]
    for j in range(1,n):
        s[j]=max(s[j-1],s[j])+a[j]
    print(s[-1],end=' ')

m, n = map(int, input().split())
t = [[0] * (n + 1)]
for i in range(m):
    t.append([0] + list(map(int, input().split())))
fin = []
for i in range(n + 1):
    fin.append([0] * (m + 1))
for i in range(1, n + 1):
    for j in range(1, m + 1):
        fin[i][j] = max(fin[i][j - 1], fin[i - 1][j]) + t[j][i]
print(' '.join(map(str, fin[n][1:])))

import sys

m, n = map(int, sys.stdin.readline().split())

latestStartTime = [0 for i in range(n)]

for i in range(m):
  picture = [int(s) for s in sys.stdin.readline().split()]

  for j in range(n): 
    if j > 0 and latestStartTime[j-1] > latestStartTime[j]:
      latestStartTime[j] = latestStartTime[j-1]
    latestStartTime[j] += picture[j]
  if i > 0:
    print(" ", end="")
  print(latestStartTime[n-1], end="")
print()
  
  

m,n=map(int, input().split())
a=[0]*8;
for i in range(m):
    x=list(map(int,input().split()))
    for j in range(1,n+1):
        a[j]=max(a[j], a[j-1])+x[j-1]
    print(a[n], end=' ')
        

m,n=map(int, input().split())
a=[0]*8
for i in range(m):
    x=list(map(int, input().split()))
    for j in range(1, n+1):
        a[j]=max(a[j], a[j-1])+x[j-1]
    print(a[n], end=' ')

m,n=map(int, input().split())
a=[0]*8
for i in range(m):
    x=list(map(int, input().split()))
    for j in range(1, n+1):
        a[j]=max(a[j], a[j-1])+x[j-1]
    print(a[n], end=' ') 

m, n=map(int, input().split())
a=[0]*8
for i in range(m):
    x=list(map(int, input().split()))
    for j in range(1, n+1):
        a[j]=max(a[j], a[j-1])+x[j-1]
    print(a[n], end=' ')

m,n=map(int, input().split())
a=[0]*8
for i in range(m):
    x=list(map(int, input().split()))
    for j in range(1,n+1):
        a[j]=max(a[j], a[j-1])+x[j-1]
    print(a[n],end=' ')

R = lambda: map(int, input().split())
m, n = R()
t = [list([0] * (m + 1)) for i in range(n + 1)]
for i in range(1, m + 1):
  a = list(R())
  for j in range(1, n + 1):
    t[j][i] = max(t[j - 1][i], t[j][i - 1]) + a[j - 1]
print(" ".join(map(str, t[n][1:])))

R = lambda:map(int, input().split())
m, n = R()
t = [0] * (n + 1)
c = []
for i in range(m):
  a = list(R())
  for j in range(n):
    t[j + 1] = max(t[j], t[j + 1]) + a[j]
  c += [str(t[n])]
print(" ".join(c))

m, n = list(map(int, input().split()))

def solve():
	painting_time = []
	finish_time = [0 for i in range(m)]
	
	for _ in range(m):
		painting_time.append(list(map(int, input().split())))

	for i in range(n):
		free_at = 0
		for j in range(m):
			start = max(free_at, finish_time[j])
			finish_time[j] = start + painting_time[j][i]
			free_at = finish_time[j]
	
	return finish_time

def __starting_point():
	print(*solve())

__starting_point()