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: EASY
Tags: Dynamic programming

Implementation

Complete search
Skill types: Dynamic programming

Complete search

Starter code:

Solutions:
(x, y) = input().split()
x = int(x)
y = int(y)
matrix = []
for i in range(0, x):
	row = []
	var = input().split()
	row = [int(x) for x in var]
	matrix.append(row)
finishedpainter = [0 for y in range(x)]
for i in range(0, y):
	free = 0
	for j in range(0, x):
		inicio = max(free, finishedpainter[j])
		finishedpainter[j] = inicio + matrix[j][i]
		free = finishedpainter[j]
retorno = ''
for i in range(0, x):
	if i == x - 1:
		retorno += str(finishedpainter[i])
		continue
	retorno += str(finishedpainter[i]) + ' '
print(retorno)


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


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
import copy
import time
starttime = time.time()
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def L():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
try:
	sys.setrecursionlimit(int(pow(10, 6)))
	sys.stdin = open('input.txt', 'r')
except:
	pass
(m, n) = L()
A = [L() for i in range(m)]
dp = [[0 for i in range(n)] for j in range(m)]
dp[0][0] = A[0][0]
for i in range(1, m):
	dp[i][0] = A[i][0] + dp[i - 1][0]
for i in range(1, n):
	dp[0][i] = dp[0][i - 1] + A[0][i]
for j in range(1, n):
	for i in range(1, m):
		dp[i][j] = max(dp[i - 1][j], dp[i][j - 1]) + A[i][j]
x = []
for i in range(m):
	x.append(dp[i][-1])
print(*x)
endtime = time.time()


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


__author__ = 'Juan Barros'

def solve(M, m, n):
	tempoFinal = [0] * m
	for i in range(n):
		livre = 0
		for j in range(m):
			inicio = max(livre, tempoFinal[j])
			tempoFinal[j] = inicio + M[j][i]
			livre = tempoFinal[j]
	print(*tempoFinal, sep=' ')
(m, n) = map(int, input().split())
aux = []
for i in range(m):
	aux.append(list(map(int, input().split())))
solve(aux, m, n)


(pictures, painters) = map(int, input().split())
dp = []
for i in range(pictures):
	times = list(map(int, input().split()))
	if len(dp) == 0:
		for t in range(painters):
			if t == 0:
				continue
			times[t] += times[t - 1]
		dp.append(times)
	else:
		for j in range(painters):
			if j == 0:
				times[j] += dp[-1][0]
			else:
				times[j] += max(dp[-1][j], times[j - 1])
		dp.append(times)
v = ' '.join([str(dp[i][-1]) for i in range(pictures)])
print(v)


(m, n) = map(int, input().split())
tij = [[int(c) for c in input().split()] for _ in range(m)]
ans = [tij[0][0]]
for i in range(1, m):
	tij[i][0] += tij[i - 1][0]
	ans.append(tij[i][0])
for j in range(n - 1):
	ans = [tij[0][j] + tij[0][j + 1]]
	for i in range(m - 1):
		start = max(ans[-1], tij[i + 1][j])
		ans.append(start + tij[i + 1][j + 1])
	for i in range(m):
		tij[i][j + 1] = ans[i]
print(*ans)


import math
L = lambda : list(map(int, input().split()))
M = lambda : map(int, input().split())
I = lambda : int(input())
(m, n) = M()
a = [0] * n
l = []
for i in range(m):
	r = L()
	a[0] += r[0]
	for j in range(1, n):
		a[j] = max(a[j - 1], a[j]) + r[j]
	l.append(a[-1])
print(*l)


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


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()


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


(m, n) = map(int, input().split())
matrix = [[] * n for _ in range(m)]
for i in range(m):
	matrix[i] = list(map(int, input().split()))
first_pos = 0
for j in range(1, m):
	matrix[j][first_pos] += matrix[j - 1][first_pos]
for k in range(1, n):
	matrix[first_pos][k] += matrix[first_pos][k - 1]
for l in range(1, m):
	for h in range(1, n):
		matrix[l][h] += max(matrix[l - 1][h], matrix[l][h - 1])
for elem in range(m):
	print(matrix[elem][n - 1], end=' ')


(n, m) = map(int, input().split())
color = [0] * (n + 1)
t = [[] for i in range(m)]
for i in range(n):
	for (p, j) in enumerate(map(int, input().split())):
		t[p].append(j)
for j in range(1, n):
	t[0][j] += t[0][j - 1]
for i in range(1, m):
	for j in range(n):
		if j == 0:
			t[i][j] += t[i - 1][j]
		else:
			t[i][j] += max(t[i - 1][j], t[i][j - 1])
[print(i, end=' ') for i in t[-1]]


(n, m) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
b = [0] * 5
ans = []
for i in range(n):
	t = 0
	for j in range(m):
		if t < b[j]:
			t = b[j]
		t += a[i][j]
		b[j] = t
	ans.append(b[m - 1])
print(*ans)


(x, y) = map(int, input().split())
matriz = [[0 for i in range(y)] for i in range(x)]
lista = []
if y <= 1:
	for c in range(x):
		z = int(input())
		if c > 0:
			matriz[c][0] = matriz[c - 1][0] + z
		else:
			matriz[c][0] = z
else:
	for c in range(x):
		z = list(map(int, input().split()))
		lista.append(z)
		if c == 0:
			matriz[c][0] = z[0]
		else:
			matriz[c][0] = matriz[c - 1][0] + z[0]
	for c in range(1, y):
		matriz[0][c] = lista[0][c] + matriz[0][c - 1]
msg = ''
if y != 1:
	for i in range(1, x):
		for j in range(1, y):
			if matriz[i][j] != 0:
				pass
			elif matriz[i - 1][j] >= matriz[i][j - 1]:
				matriz[i][j] = matriz[i - 1][j] + lista[i][j]
			elif matriz[i - 1][j] < matriz[i][j - 1]:
				matriz[i][j] = matriz[i][j - 1] + lista[i][j]
for c in range(x):
	msg += str(matriz[c][-1]) + ' '
print(msg.strip())


import sys
inf = float('inf')

def get_array():
	return list(map(int, sys.stdin.readline().strip().split()))

def get_ints():
	return map(int, sys.stdin.readline().strip().split())

def input():
	return sys.stdin.readline().strip()
(n, m) = get_ints()
mat = []
for i in range(n):
	mat.append(get_array())
for i in range(n):
	for j in range(m):
		if i == 0 and j == 0:
			continue
		elif i == 0 and j > 0:
			mat[i][j] += mat[i][j - 1]
		elif j == 0 and i > 0:
			mat[i][j] += mat[i - 1][j]
		else:
			mat[i][j] += max(mat[i - 1][j], mat[i][j - 1])
ans = []
for i in mat:
	ans.append(i[-1])
print(*ans)


import os
import sys
from io import BytesIO, IOBase

def main():
	(m, n) = map(int, input().split())
	arr = []
	for _ in range(m):
		arr.append(list(map(int, input().split())))
	ans = []
	for i in range(1, n):
		arr[0][i] += arr[0][i - 1]
	ans.append(arr[0][-1])
	for i in range(1, m):
		arr[i][0] += arr[i - 1][0]
		for j in range(1, n):
			arr[i][j] += max(arr[i - 1][j], arr[i][j - 1])
		ans.append(arr[i][-1])
	print(*ans)
BUFSIZE = 8192

class FastIO(IOBase):
	newlines = 0

	def __init__(self, file):
		self._fd = file.fileno()
		self.buffer = BytesIO()
		self.writable = 'x' in file.mode or 'r' not in file.mode
		self.write = self.buffer.write if self.writable else None

	def read(self):
		while True:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			if not b:
				break
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines = 0
		return self.buffer.read()

	def readline(self):
		while self.newlines == 0:
			b = os.read(self._fd, max(os.fstat(self._fd).st_size, BUFSIZE))
			self.newlines = b.count(b'\n') + (not b)
			ptr = self.buffer.tell()
			(self.buffer.seek(0, 2), self.buffer.write(b), self.buffer.seek(ptr))
		self.newlines -= 1
		return self.buffer.readline()

	def flush(self):
		if self.writable:
			os.write(self._fd, self.buffer.getvalue())
			(self.buffer.truncate(0), self.buffer.seek(0))

class IOWrapper(IOBase):

	def __init__(self, file):
		self.buffer = FastIO(file)
		self.flush = self.buffer.flush
		self.writable = self.buffer.writable
		self.write = lambda s: self.buffer.write(s.encode('ascii'))
		self.read = lambda : self.buffer.read().decode('ascii')
		self.readline = lambda : self.buffer.readline().decode('ascii')
(sys.stdin, sys.stdout) = (IOWrapper(sys.stdin), IOWrapper(sys.stdout))
input = lambda : sys.stdin.readline().rstrip('\r\n')
main()


(m, n) = [int(x) for x in input().split()]
T = []
for x in range(0, m):
	T.append([int(x) for x in input().split()])
TimeA = []
sum = 0
for i in range(0, m):
	B = []
	sum += T[i][0]
	B.append(sum)
	for j in range(0, n - 1):
		B.append(-1)
	TimeA.append(B)

def Time(x, n):
	if TimeA[x][n] == -1:
		if x == 0:
			TimeA[x][n] = Time(x, n - 1) + T[x][n]
		else:
			TimeA[x][n] = max(Time(x, n - 1), Time(x - 1, n)) + T[x][n]
	return TimeA[x][n]
for i in range(0, m):
	print(Time(i, n - 1), end=' ')


(m, n) = map(int, input().split())
l = []
for i in range(m):
	s = list(map(int, input().split()))
	l.append(s)
dp = [[0 for i in range(n)] for j in range(m)]
dp[0][0] = l[0][0]
for i in range(1, n):
	dp[0][i] = dp[0][i - 1] + l[0][i]
for i in range(1, m):
	dp[i][0] = dp[i - 1][0] + l[i][0]
	for j in range(1, n):
		dp[i][j] = dp[i][j - 1] + l[i][j]
		if dp[i - 1][j] - dp[i][j - 1] > 0:
			dp[i][j] += dp[i - 1][j] - dp[i][j - 1]
for i in range(m - 1):
	print(dp[i][n - 1], end=' ')
print(dp[m - 1][n - 1])


(m, n) = map(int, input().split())
t = []
for i in range(m):
	t.append(list(map(int, input().split())))
delay = 0
s = [0] * n
s[0] = t[0][0]
for i in range(m):
	if i != 0:
		delay = s[0]
		s[0] += t[i][0]
		for j in range(n - 1):
			if s[j + 1] < 0:
				s[j + 1] = 0
			s[j + 1] = t[i - 1][j + 1] + s[j + 1] - t[i][j]
			if s[j] < 0:
				s[j + 1] += s[j]
			if s[j + 1] > 0:
				delay += s[j + 1]
	print(sum(t[i]) + delay, end=' ')
print()


import sys
(m, n) = map(int, input().split())
a = [[] * n for i in range(m)]
for i in range(m):
	a[i] = list(map(int, input().split()))
for i in range(1, m):
	a[i][0] += a[i - 1][0]
for i in range(1, n):
	a[0][i] += a[0][i - 1]
for i in range(1, m):
	for j in range(1, n):
		a[i][j] += max(a[i - 1][j], a[i][j - 1])
for i in range(m):
	sys.stdout.write(str(a[i][n - 1]) + ' ')


def zip_sorted(a, b):
	(a, b) = zip(*sorted(zip(a, b)))
	sorted(zip(a, b), key=lambda x: x[1])
	return (a, b)
import sys
input = sys.stdin.readline
I = lambda : list(map(int, input().split()))
S = lambda : list(map(str, input().split()))
(m, n) = I()
b = []
c = [0] * m
for t1 in range(m):
	a = I()
	b.append(a)
c[0] = c[0] + b[0][0]
for i in range(1, m):
	c[i] = c[i] + b[i][0] + c[i - 1]
for j in range(1, n):
	for k in range(m):
		if k != 0:
			if c[k] < c[k - 1]:
				c[k] = c[k - 1] + b[k][j]
			else:
				c[k] = c[k] + b[k][j]
		else:
			c[k] = c[k] + b[k][j]
print(*c)


(m, n) = list(map(int, input().split()))
mat = []
for i in range(m):
	mat.append(list(map(int, input().split())))
arr = []
for i in range(n):
	temp = []
	for j in range(m):
		temp.append(mat[j][i])
	arr.append(temp)
for i in range(1):
	for j in range(1, len(arr[i])):
		arr[i][j] += arr[i][j - 1]
for i in range(1, len(arr)):
	arr[i][0] = arr[i - 1][0] + arr[i][0]
	for j in range(1, len(arr[i])):
		arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]) + arr[i][j]
temp = arr[-1]
print(*temp)


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


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


(n, m) = map(int, input().split())
mat = []
for i in range(n):
	mat.append([int(i) for i in input().split()])
ans = [[0 for i in range(n + 1)] for k in range(m + 1)]
get = [[0 for i in range(n + 1)] for k in range(m + 1)]
for j in range(m):
	for i in range(n):
		ans[j][i] = max(ans[j - 1][i], ans[j][i - 1]) + mat[i][j]
for i in range(n):
	print(ans[m - 1][i], end=' ')


temp = list(map(int, input().split(' ')))
m = temp[0]
n = temp[1]
dp = [[0] * n]
for i in range(m):
	temp1 = list(map(int, input().split(' ')))
	dp.append(temp1)
for painter in range(n):
	for picture in range(1, m + 1):
		if painter == 0:
			dp[picture][painter] += dp[picture - 1][painter]
		else:
			dp[picture][painter] = max(dp[picture - 1][painter] + dp[picture][painter], dp[picture][painter - 1] + dp[picture][painter])
answer = str(dp[1][-1])
for subarray_index in range(2, m + 1):
	answer += ' ' + str(dp[subarray_index][-1])
print(answer)


(m, n) = map(int, input().split())
ans = [0 for _ in range(n)]
res = []
for i in range(m):
	a = list(map(int, input().split()))
	for j in range(n):
		if j > 0:
			ans[j] = max(ans[j - 1], ans[j])
		ans[j] += a[j]
	res.append(ans[n - 1])
print(*res)


import sys
(m, n) = map(int, sys.stdin.readline().split())
a = n * [0]
ans = []
for i in range(m):
	x = list(map(int, sys.stdin.readline().split()))
	for j in range(n):
		if j == 0:
			a[j] += x[j]
		else:
			a[j] = max(a[j - 1], a[j]) + x[j]
		if j == n - 1:
			ans.append(a[-1])
print(*ans)


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


import sys
(m, n) = map(int, sys.stdin.readline().split())
a = n * [0]
for i in range(m):
	x = list(map(int, sys.stdin.readline().split()))
	for j in range(n):
		if j == 0:
			a[j] += x[j]
		else:
			a[j] = max(a[j - 1], a[j]) + x[j]
		if j == n - 1:
			sys.stdout.write(str(a[-1]) + ' ')


(m, n) = list(map(int, input().rstrip().split()))
t = []
for _ in range(m):
	li = list(map(int, input().rstrip().split()))
	t += [li]
pic = [0] * m
pic[0] = t[0][0]
for j in range(n):
	for i in range(m):
		if i == 0 and j > 0:
			pic[i] += t[i][j]
		elif j == 0 and i > 0:
			pic[i] = pic[i - 1] + t[i][j]
		elif i > 0 and j > 0:
			pic[i] = max(pic[i - 1], pic[i]) + t[i][j]
for i in range(m):
	print(pic[i], end=' ')


(paint, painter) = map(int, input().split())
prev = [0] * painter
x = list(map(int, input().split()))
for i in range(painter):
	if i != 0:
		prev[i] += x[i] + prev[i - 1]
	else:
		prev[i] += x[i]
print(prev[i])
for i in range(paint - 1):
	x = list(map(int, input().split()))
	for j in range(painter):
		if j == 0:
			pre = prev[j]
		else:
			pre = max(prev[j], prev[j - 1])
		prev[j] = pre + x[j]
	print(prev[j])


(m, n) = list(map(int, input().split()))
t = [list(map(int, input().split())) for _ in range(m)]
tt = []
for i in range(m):
	thisRow = []
	for j in range(n):
		if j == 0 and i == 0:
			thisRow.append(t[i][j])
		elif j == 0:
			thisRow.append(tt[i - 1][j] + t[i][j])
		elif i == 0:
			thisRow.append(thisRow[j - 1] + t[i][j])
		else:
			thisRow.append(max(tt[i - 1][j], thisRow[j - 1]) + t[i][j])
	tt.append(thisRow)
ans = [row[-1] for row in tt]
print(' '.join(map(str, ans)))


class CodeforcesTask416BSolution:

	def __init__(self):
		self.result = ''
		self.m_n = []
		self.pictures = []

	def read_input(self):
		self.m_n = [int(x) for x in input().split(' ')]
		for x in range(self.m_n[0]):
			self.pictures.append([int(y) for y in input().split(' ')])

	def process_task(self):
		if self.m_n[0] > 1:
			for x in range(self.m_n[0] - 1):
				self.pictures[x + 1][0] += self.pictures[x][0]
			for n in range(self.m_n[1] - 1):
				self.pictures[0][n + 1] += self.pictures[0][n]
			for n in range(self.m_n[1] - 1):
				for x in range(self.m_n[0] - 1):
					self.pictures[x + 1][n + 1] += max(self.pictures[x][n + 1], self.pictures[x + 1][n])
			for x in range(self.m_n[0]):
				print(self.pictures[x][self.m_n[1] - 1], end=' ')
		else:
			self.result = str(sum(self.pictures[0]))

	def get_result(self):
		return self.result
Solution = CodeforcesTask416BSolution()
Solution.read_input()
Solution.process_task()
print(Solution.get_result())


(n, m) = map(int, input().split())
l = []
b = [0] * m
for i in range(n):
	l.append(list(map(int, input().split())))
for i in range(n):
	for j in range(m):
		if j == 0:
			b[0] += l[i][0]
		elif b[j] >= b[j - 1]:
			b[j] += l[i][j]
		else:
			b[j] = b[j - 1] + l[i][j]
	print(b[-1], end=' ')


import math as mt
import sys, string, bisect
input = sys.stdin.readline
import random
from collections import deque, defaultdict
L = lambda : list(map(int, input().split()))
Ls = lambda : list(input().split())
M = lambda : map(int, input().split())
I = lambda : int(input())
(m, n) = M()
l = [[0] * n]
for i in range(m):
	l.append(L())
for i in range(1, m + 1):
	for j in range(n):
		if j == 0:
			l[i][j] += l[i - 1][j]
		else:
			p = l[i][j - 1] + l[i][j]
			q = l[i][j] + l[i - 1][j]
			l[i][j] = max(p, q)
	print(l[i][n - 1], end=' ')


from sys import stdin
(m, n) = [int(x) for x in stdin.readline().split()]
t = [[int(x) for x in stdin.readline().split()] for _ in range(m)]
curr_time = 0
free_at = [curr_time] * 5
for i in range(m):
	for j in range(n):
		if j > 0:
			free_at[j] = max(free_at[j - 1], free_at[j])
		free_at[j] += t[i][j]
		curr_time = max(curr_time, free_at[j])
	print(curr_time, end=' ')


from sys import stdin, stdout, setrecursionlimit

class Tail_Recursion_Optimization:

	def __init__(self, RECURSION_LIMIT, STACK_SIZE):
		setrecursionlimit(RECURSION_LIMIT)
		threading.stack_size(STACK_SIZE)
		return None

class SOLVE:

	def solve(self):
		R = stdin.readline
		W = stdout.write
		ans = []
		(m, n) = [int(x) for x in R().split()]
		time = []
		for i in range(m):
			tmp_time = [int(x) for x in R().split()]
			if i == 0:
				time.append(tmp_time[0])
				for j in range(1, n):
					time.append(time[j - 1] + tmp_time[j])
			else:
				tmp_time[0] += time[0]
				for j in range(1, n):
					tmp_time[j] += max(tmp_time[j - 1], time[j])
				time = tmp_time.copy()
			ans.append(str(time[n - 1]))
		W(' '.join(ans))
		return 0

def main():
	s = SOLVE()
	s.solve()
main()


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


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


(pinturas, pintores) = [int(x) for x in input().split()]
infos = []
for _ in range(pinturas):
	infos.append([int(x) for x in input().split()])
for i in range(1, pinturas):
	infos[i][0] += infos[i - 1][0]
for i in range(1, pintores):
	infos[0][i] += infos[0][i - 1]
if pintores > 1:
	for i in range(1, pinturas):
		for j in range(1, pintores):
			anterior = infos[i - 1][j]
			atual = infos[i][j - 1]
			infos[i][j] = max(anterior, atual) + infos[i][j]
print(' '.join([str(x[-1]) for x in infos]))


(m, n) = map(int, input().split())
r = [0] * m
temp = [0] * n
for i in range(m):
	x = list(map(int, input().split()))
	temp[0] += x[0]
	for k in range(1, n):
		temp[k] = max(temp[k - 1], temp[k]) + x[k]
	r[i] = temp[len(temp) - 1]
s = ''
for i in range(m):
	s += str(r[i]) + ' '
print(s[:len(s) - 1])


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):
	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)


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


from collections import defaultdict

def main():
	(m, n) = list(map(int, input().split()))
	t = [0] * (n + 1)
	ans = ''
	for i in range(m):
		tmp = [0]
		tmp2 = list(map(int, input().split()))
		for i in range(n):
			tmp.append(tmp2[i])
		for i in range(n):
			tmp[i + 1] += max(tmp[i], t[i + 1])
		t = tmp.copy()
		ans += str(tmp[-1]) + ' '
	print(ans)
main()


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


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) = map(int, input().split())
t = [[]] * m
ans = [[]] * m
for i in range(m):
	t[i] = list(map(int, input().split()))
	ans[i] = [0] * n
for i in range(m):
	for j in range(n):
		a1 = ans[i - 1][j] if i > 0 else 0
		a2 = ans[i][j - 1] if j > 0 else 0
		ans[i][j] = max(a1, a2) + t[i][j]
print(' '.join(map(lambda o: str(ans[o][n - 1]), range(m))))


import sys
from math import *

def minp():
	return sys.stdin.readline().strip()

def mint():
	return int(minp())

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


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


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


(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])


(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:])))


from sys import stdin, stdout
from math import gcd, sqrt, factorial, pi, inf
from collections import deque, defaultdict
input = stdin.readline
R = lambda : map(int, input().split())
I = lambda : int(input())
S = lambda : input().rstrip('\n')
L = lambda : list(R())
P = lambda x: stdout.write(str(x) + '\n')
lcm = lambda x, y: x * y // gcd(x, y)
hg = lambda x, y: (y + x - 1) // x * x
pw = lambda x: 1 if x == 1 else 1 + pw(x // 2)
chk = lambda x: chk(x // 2) if not x % 2 else True if x == 1 else False
sm = lambda x: (x ** 2 + x) // 2
N = 10 ** 9 + 7
(m, n) = R()
a = [0] * n
for _ in range(m):
	x = L() + [0]
	for i in range(n):
		x[i] += max(a[i], x[i - 1])
	a = x[:-1]
	print(a[-1])


(m, n) = map(int, input().split())
dp = [[int(i) for i in input().split()] for j in range(m)]
for j in range(n):
	for i in range(m):
		if j == 0:
			if i != 0:
				dp[i][j] += dp[i - 1][j]
		elif i != 0:
			dp[i][j] += max(dp[i][j - 1], dp[i - 1][j])
		else:
			dp[i][j] += dp[i][j - 1]
for i in range(m):
	print(dp[i][n - 1], end=' ')


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


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


read_many = lambda type_: list(map(type_, input().split()))
(m, n) = read_many(int)
time_table = []
time_table.append([0 for _ in range(n)])
for _ in range(m):
	time_table.append(read_many(int))
turn_cols_to_rows = lambda matrix: [list(t) for t in zip(*matrix)]
time_table = turn_cols_to_rows(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:])))


(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) = [int(c) for c in input().split()]
t = [[0] * (n + 1)]
for i in range(m):
	t.append([0] + [int(c) for c in input().split()])
for i in range(1, m + 1):
	for j in range(1, n + 1):
		found = max(t[i - 1][j], t[i][j - 1])
		t[i][j] = found + t[i][j]
	print(t[i][j])


(m, n) = 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
print(*solve())


(n, m) = map(int, input().split())
l = []
hash = {}
for i in range(1, m + 1):
	hash[i] = 0
for i in range(n):
	k = list(map(int, input().split()))
	l.append(k)
for i in range(n):
	for j in range(m):
		if j != 0:
			if hash[j] >= hash[j + 1]:
				hash[j + 1] += hash[j] - hash[j + 1] + l[i][j]
			else:
				hash[j + 1] += l[i][j]
		else:
			hash[j + 1] += l[i][j]
	print(hash[m], end=' ')


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


import math, sys
from collections import defaultdict, deque
import bisect as bi

def yes():
	print('YES')

def no():
	print('NO')

def I():
	return int(sys.stdin.readline())

def In():
	return map(int, sys.stdin.readline().split())

def Sn():
	return sys.stdin.readline().strip()

def dict(a):
	d = {}
	for x in a:
		if d.get(x, -1) != -1:
			d[x] += 1
		else:
			d[x] = 1
	return d

def find_gt(a, x):
	i = bi.bisect_left(a, x)
	if i != len(a):
		return i
	else:
		return -1

def main():
	try:
		(m, n) = In()
		l = [list(In()) for i in range(m)]
		dp = [[0 for i in range(m)] for i in range(n)]
		cur = 0
		for i in range(m):
			cur += l[i][0]
			dp[0][i] = cur
		for i in range(1, n):
			cur = 0
			for j in range(m):
				if cur < dp[i - 1][j]:
					cur = dp[i - 1][j] + l[j][i]
				else:
					cur += l[j][i]
				dp[i][j] = cur
		print(*dp[-1])
	except:
		pass
M = 998244353
P = 1000000007
for _ in range(1):
	main()


(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()


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


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


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


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


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


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


(m, n) = map(int, input().split())
t = list(map(int, input().split()))
dp = [0] * n
dp[0] = t[0]
for i in range(1, n):
	dp[i] = dp[i - 1] + t[i]
ans = [dp[-1]]
for i in range(1, m):
	t = list(map(int, input().split()))
	dp[0] += t[0]
	for i in range(1, n):
		if dp[i - 1] <= dp[i]:
			dp[i] += t[i]
		else:
			dp[i] += t[i] + dp[i - 1] - dp[i]
	ans.append(dp[-1])
print(*ans)


table = []
(n, m) = list(map(int, input().split()))
for i in range(n):
	painters = list(map(int, input().split()))
	table.append(painters)
dp = [[table[0][0]]]
result = []
for i in range(n):
	for j in range(m):
		if i == 0 and j > 0:
			dp[i].append(table[i][j] + dp[i][j - 1])
		elif i > 0 and j == 0:
			dp.append([table[i][j] + dp[i - 1][j]])
		elif i > 0 and j > 0:
			max_time = max(dp[i - 1][j], dp[i][j - 1])
			dp[i].append(table[i][j] + max_time)
		if j == m - 1:
			result.append(str(dp[i][j]))
print(' '.join(result))


solution = []
(n_pic, n_paint) = list(map(int, input().split()))
times_paint = []
for i in range(n_paint + 1):
	solution.append([0] * (n_pic + 1))
for i in range(n_pic):
	time_paint = list(map(int, input().split()))
	times_paint.append(time_paint)
for i in range(1, n_paint + 1):
	for k in range(1, n_pic + 1):
		maxToEvaluate = max(solution[i][k - 1], solution[i - 1][k])
		solution[i][k] = maxToEvaluate + times_paint[k - 1][i - 1]
respostaString = []
for i in range(1, len(solution[n_paint])):
	respostaString.append(solution[n_paint][i])
print(' '.join(map(str, respostaString)).strip())


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


import sys
input = sys.stdin.readline
(n, m) = map(int, input().split())
times = []
for i in range(n):
	time = list(map(int, input().split()))
	times.append(time)
ans = [0 for i in range(n)]
for i in range(m):
	ht = 0
	for j in range(n):
		s = max(ht, ans[j])
		ans[j] = s + times[j][i]
		ht = ans[j]
for i in range(n):
	print(ans[i], end=' ')


(m, n) = [int(x) for x in input().split()]
times = []
for i in range(m):
	temp = [int(x) for x in input().split()]
	times.append(temp)
pictures = [0] * m
for j in range(n):
	for i in range(m):
		if i == 0:
			pictures[i] = pictures[i] + times[i][j]
		else:
			pictures[i] = max(pictures[i], pictures[i - 1]) + times[i][j]
for p in pictures:
	print(p, end=' ')
print()


from sys import stdin, stdout
(a, b) = map(int, stdin.readline().split())
z = [list(map(int, stdin.readline().split())) for _ in ' ' * a]
k = [[0] * b for _ in ' ' * a]
ans = [''] * a
for i in range(a):
	if i == 0:
		for j in range(b):
			k[i][j] += k[i][j - 1] + z[i][j]
	else:
		for j in range(b):
			if j == 0:
				k[i][j] += k[i - 1][j] + z[i][j]
			else:
				k[i][j] = max(k[i - 1][j], k[i][j - 1]) + z[i][j]
	ans[i] = str(k[i][b - 1])
stdout.write(' '.join(ans))


(qtdPictures, qtdPainters) = input().split()
qtdPictures = int(qtdPictures)
qtdPainters = int(qtdPainters)
finish = []
pictures = []
for i in range(qtdPictures):
	pictures.append([*map(int, input().split())])
pictures[0][0] = int(pictures[0][0])
for i in range(1, qtdPictures):
	pictures[i][0] = int(pictures[i][0]) + pictures[i - 1][0]
for i in range(1, qtdPainters):
	pictures[0][i] += pictures[0][i - 1]
if qtdPainters > 1:
	for i in range(1, qtdPictures):
		for j in range(1, qtdPainters):
			accAnterior = pictures[i - 1][j]
			accAtual = pictures[i][j - 1]
			pictures[i][j] = max(accAnterior, accAtual) + pictures[i][j]
resp = ''
for i in range(qtdPictures):
	resp += str(pictures[i][-1])
	if i < qtdPictures - 1:
		resp += ' '
print(resp)


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


(m, n) = map(int, input().split())
t = list()
for i in range(m):
	t.append(list(map(int, input().split())))
for col in range(n):
	for row in range(m):
		left = 0 if col == 0 else t[row][col - 1]
		up = 0 if row == 0 else t[row - 1][col]
		start = max(left, up)
		t[row][col] = start + t[row][col]
for row in range(m):
	print(t[row][n - 1])


(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) = map(int, input().strip().split())
final = []
for _ in range(m):
	l = list(map(int, input().split()))
	final.append(l)
checkstart = 0
checkend = 0
for i in range(1, m):
	final[i][0] += final[i - 1][0]
for i in range(1, n):
	final[0][i] += final[0][i - 1]
for i in range(1, m):
	for j in range(1, n):
		final[i][j] += max(final[i][j - 1], final[i - 1][j])
ans = []
for i in range(m):
	ans.append(final[i][n - 1])
print(*ans)


(m, n) = map(int, input().split())
a = []
for i in range(m):
	p = [int(j) for j in input().split()]
	a.append(p)
for j in range(1, m):
	a[j][0] += a[j - 1][0]
for i in range(1, n):
	a[0][i] += a[0][i - 1]
	for j in range(1, m):
		a[j][i] += max(a[j - 1][i], a[j][i - 1])
for i in range(m):
	p = int(a[i][n - 1])
	print(p)


(n, m) = map(int, input().split())
painters = [0] * (m + 1)
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
ans = []
for i in range(n):
	for j in range(m):
		if i == 0:
			if j == 0:
				painters[j + 1] += l[i][j]
			else:
				painters[j + 1] = painters[j] + l[i][j]
		elif j == 0:
			painters[j + 1] += l[i][j]
		elif painters[j] <= painters[j + 1]:
			painters[j + 1] += l[i][j]
		else:
			painters[j + 1] = painters[j] + l[i][j]
	ans.append(painters[m])
print(*ans)


(m, n) = [int(c) for c in input().split()]
ts = [[0] * (n + 1)]
for i in range(m):
	ts.append([0] + [int(c) for c in input().split()])
for i in range(1, m + 1):
	for j in range(1, n + 1):
		ts[i][j] = max(ts[i - 1][j], ts[i][j - 1]) + ts[i][j]
	print(ts[i][j])


def mi():
	return map(int, input().split())
(m, n) = mi()
a = [[0] * m for i in range(n)]
t = 0
l = list(mi())
for i in range(n):
	a[i][0] = l[i] + (i != 0) * a[i - 1][0]
print(sum(l), end=' ')
for i in range(1, m):
	l = list(mi())
	for j in range(n):
		if j == 0:
			t = a[j][i - 1] + l[j]
		else:
			t = max(a[j - 1][i], a[j][i - 1]) + l[j]
		a[j][i] = t
	print(t, end=' ')


l = input().split()
m = int(l[0])
n = int(l[1])
l = []
for i in range(m):
	lo = input().split()
	li = [int(i) for i in lo]
	l.append(li)
arr = [[0 for i in range(n)] for i in range(m)]
ok = 0
for i in range(m):
	ok += l[i][0]
	arr[i][0] = ok
for i in range(1, n):
	curr = 0
	for j in range(m):
		curr = max(curr, arr[j][i - 1])
		curr += l[j][i]
		arr[j][i] = curr
for i in range(m):
	print(arr[i][-1], end=' ')


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
(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())
arr = []
for _ in range(m):
	arr += [list(map(int, input().split()))]
dp = [0] * m
for i in range(n):
	dp[0] += arr[0][i]
	for j in range(1, m):
		dp[j] = arr[j][i] + max(dp[j - 1], dp[j])
print(*dp)


import re
import inspect
from sys import argv, exit

def rstr():
	return input()

def rint():
	return int(input())

def rints(splitchar=' '):
	return [int(i) for i in input().split(splitchar)]

def rstrs(splitchar=' '):
	return [i for i in input().split(splitchar)]

def varnames(obj, namespace=globals()):
	return [name for name in namespace if namespace[name] is obj]

def pvar(var, override=False):
	prnt(varnames(var), var)

def prnt(*args, override=False):
	if '-v' in argv or override:
		print(*args)
(m, n) = rints()
times = [rints() for i in range(m)]
for i in range(len(times)):
	time = times[i]
	prev_time = times[i - 1] if i - 1 >= 0 else None
	next_time = times[i + 1] if i + 1 < len(times) else None
	for j in range(len(time)):
		prev_painter = time[j - 1] if j - 1 >= 0 else None
		prev_painting = prev_time[j] if prev_time else None
		if prev_painter and prev_painting:
			times[i][j] = times[i][j] + max(prev_painter, prev_painting)
		elif prev_painter:
			times[i][j] = times[i][j] + prev_painter
		elif prev_painting:
			times[i][j] = times[i][j] + prev_painting
total = 0
final = []
for time in times:
	final.append(time[-1])
print(' '.join([str(i) for i in final]))


import sys
import heapq
from math import *
from collections import defaultdict as dd
from collections import deque
from collections import Counter as c
from itertools import combinations as comb
from bisect import bisect_left as bl, bisect_right as br, bisect
mod = pow(10, 9) + 7
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(var):
	sys.stdout.write(var)

def l():
	return list(map(int, data().split()))

def sl():
	return list(map(str, data().split()))

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [[val for i in range(n)] for j in range(m)]
(m, n) = sp()
a = l1d(n)
for i in range(m):
	arr = l()
	for j in range(n):
		if j > 0:
			a[j] = max(a[j], a[j - 1])
		a[j] += arr[j]
	print(a[n - 1])


def arr_inp():
	return [int(x) for x in stdin.readline().split()]

def get_col(arr, i):
	return [row[i] for row in arr]

def arr_sum(ar):
	ar.insert(0, 0)
	return list(accumulate(ar, lambda x, y: x + y))
from itertools import accumulate
from sys import stdin
(m, n) = arr_inp()
arr = [arr_inp() for i in range(m)]
ans = arr_sum(get_col(arr, 0))[1:]
if m == 1:
	print(sum(arr[0]))
elif n == 1:
	print(*ans)
else:
	for i in range(1, n):
		free = 0
		for j in range(m):
			ans[j] = max(free, ans[j]) + arr[j][i]
			free = ans[j]
	print(*ans)


from sys import stdin, stdout
ii1 = lambda : int(stdin.readline().strip())
is1 = lambda : stdin.readline().strip()
iia = lambda : list(map(int, stdin.readline().strip().split()))
isa = lambda : stdin.readline().strip().split()
mod = 1000000007
(m, n) = iia()
arr = []
for i in range(m):
	arr.append(iia())
time = [0] * n
for i in range(m):
	for j in range(n):
		if j > 0:
			t = max(time[j] - time[j - 1], 0)
			time[j] = t + time[j - 1] + arr[i][j]
		else:
			time[j] += arr[i][j]
	print(time[-1], end=' ')
print()


def main():
	(m, n) = map(int, input().split(' '))
	t = []
	for i in range(m):
		l = list(map(int, input().split(' ')))
		t.append(l)
	f = [0] * m
	for i in range(n):
		time = 0
		for j in range(m):
			s = max(time, f[j])
			f[j] = s + t[j][i]
			time = f[j]
	print(' '.join(list(map(str, f))))
main()


(m, n) = [int(x) for x in input().split()]
tempo_pintura = []
for i in range(m):
	temp = [int(x) for x in input().split()]
	tempo_pintura.append(temp)
encerrou = [0] * m
for i in range(n):
	t1 = 0
	for j in range(m):
		t2 = max(t1, encerrou[j])
		encerrou[j] = t2 + tempo_pintura[j][i]
		t1 = encerrou[j]
print(' '.join([str(x) for x in encerrou]))


(m, n) = map(int, input().split())
t = [0] * (n + 1)
total = []
for _ in range(m):
	p_times = list(map(int, input().split()))
	for i in range(1, n + 1):
		t[i] = max(t[i], t[i - 1]) + p_times[i - 1]
	total.append(t[n])
print(*total, sep=' ')


(n, m) = map(int, input().split())
pictures = []
for i in range(n):
	pictures.append(list(map(int, input().split())))
painters = [0] * 5
ans = []
for i in range(n):
	time = 0
	for j in range(m):
		if time < painters[j]:
			time = painters[j]
		time += pictures[i][j]
		painters[j] = time
	ans.append(painters[m - 1])
print(*ans)


(m, n) = [int(x) for x in input().split()]
ans = [[0 for i in range(n)] for i in range(m)]
a = []
for i in range(m):
	a.append([int(x) for x in input().split()])
ans[0][0] = a[0][0]
for i in range(1, m):
	ans[i][0] = ans[i - 1][0] + a[i][0]
for i in range(1, n):
	ans[0][i] = ans[0][i - 1] + a[0][i]
for i in range(1, n):
	for j in range(1, m):
		if ans[j][i - 1] <= ans[j - 1][i]:
			ans[j][i] = ans[j - 1][i] + a[j][i]
		else:
			ans[j][i] = ans[j][i - 1] + a[j][i]
for i in range(m):
	print(ans[i][n - 1], end=' ')


(m, n) = map(int, input().split())
pictures_t = []
for i in range(m):
	pictures_t.append(list(map(int, input().split())))
last_work = [0, 0, 0, 0, 0]
for j in range(m):
	time = 0
	for i in range(n):
		lw = last_work[i]
		if time < lw:
			time = lw
		time += pictures_t[j][i]
		last_work[i] = time
	print(time, end=' ')


def main():
	(n, m) = map(int, input().split())
	l = [(int(input()),) for _ in range(n)] if m == 1 else list((tuple(map(int, input().split())) for _ in range(n)))
	res = [0] * n
	for a in zip(*l):
		t0 = 0
		for (i, r, t) in zip(range(n), res, a):
			if t0 < r:
				t0 = r
			t0 += t
			res[i] = t0
	print(*res)
main()


(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:])))


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


def prog():
	from sys import stdin
	(m, n) = map(int, stdin.readline().split())
	vozv = list(map(int, stdin.readline().split()))
	n -= 1
	(mas, e) = ([], 0)
	for (i, x) in enumerate(vozv):
		e += x
		mas.append(e)
	res = [e]
	for i in range(m - 1):
		lst = list(map(int, stdin.readline().split()))
		e = lst[0]
		otv = 0
		lst[0] += mas[0]
		for j in range(1, n + 1):
			(r, t) = (mas[j], lst[j - 1])
			lst[j] += max(mas[j], lst[j - 1])
		res.append(lst[n])
		mas = list(lst)
	print(*res)
prog()


import sys
import string
from collections import Counter, defaultdict
from math import fsum, sqrt, gcd, ceil, factorial
from itertools import combinations, permutations
flush = lambda : sys.stdout.flush
comb = lambda x, y: factorial(x) // factorial(y) // factorial(x - y)
ip = lambda : input()
ii = lambda : int(input())
r = lambda : map(int, input().split())
rr = lambda : list(r())
(n, k) = r()
arr = [[0] * k] + [rr() for _ in range(n)]
for i in range(1, n + 1):
	for j in range(k):
		if j == 0:
			arr[i][j] += arr[i - 1][j]
		else:
			arr[i][j] = max(arr[i - 1][j], arr[i][j - 1]) + arr[i][j]
for i in arr[1:]:
	print(i[-1], end=' ')


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


(pic, painters) = map(int, input().split())
times = [list(map(int, input().split())) for x in range(pic)]
s = ''
for i in range(pic):
	for j in range(painters):
		if i == 0:
			if j > 0:
				times[i][j] += times[i][j - 1]
		elif j == 0:
			times[i][j] += times[i - 1][j]
		else:
			times[i][j] += max(times[i - 1][j], times[i][j - 1])
	if i == pic - 1:
		s += str(times[i][painters - 1])
	else:
		s += str(times[i][painters - 1]) + ' '
print(s)


(m, n) = list(map(int, input().split()))
time = [list(map(int, input().split())) for _ in range(m)]
pass_on_time = [0] * m
for painter in range(n):
	for painting in range(m):
		if painting == 0:
			current_time = pass_on_time[painting]
		else:
			current_time = max(pass_on_time[painting], pass_on_time[painting - 1])
		time_required = time[painting][painter]
		current_time += time_required
		pass_on_time[painting] = current_time
for pass_time in pass_on_time:
	print(pass_time, end=' ')


(m, n) = list(map(int, input().split()))
a = [[0] * n for i in range(m)]
for i in range(m):
	h = list(map(int, input().rstrip().split()))
	for j in range(n):
		a[i][j] = h[j]
for i in range(1, n):
	a[0][i] = a[0][i] + a[0][i - 1]
for i in range(1, m):
	a[i][0] = a[i][0] + a[i - 1][0]
for i in range(1, n):
	for j in range(1, m):
		if a[j - 1][i] > a[j][i - 1]:
			a[j][i] += abs(a[j - 1][i] - a[j][i - 1]) + a[j][i - 1]
		else:
			a[j][i] += a[j][i - 1]
for i in range(m):
	print(a[i][-1], end=' ')


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


(m, n) = map(int, input('').split())
z = {}
for i in range(0, m):
	z[i] = list(map(int, input('').split()))
for i in range(1, n):
	z[0][i] += z[0][i - 1]
for i in range(1, m):
	z[i][0] += z[i - 1][0]
for j in range(1, n):
	for i in range(1, m):
		q = z[i - 1][j]
		if q > z[i][j - 1]:
			z[i][j] += q
		else:
			z[i][j] += z[i][j - 1]
for i in range(0, m):
	print(z[i][n - 1])


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


from itertools import accumulate
(m, n) = map(int, input().split())
t = []
for i in range(m):
	arr = list(map(int, input().split()))
	t.append(arr)
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
import math

def fn(n, m, a):
	if n == 1:
		t1 = 0
		for i in range(m):
			t1 = t1 + a[i][0]
			print(t1, end=' ')
		return 0
	t = [0] * n
	t[0] = a[0][0]
	for i in range(1, n):
		t[i] = a[0][i] + t[i - 1]
	print(t[n - 1], end=' ')
	for i in range(1, m):
		t[0] = t[0] + a[i][0]
		for j in range(n - 1):
			if t[j + 1] < t[j]:
				t[j + 1] = a[i][j + 1] + t[j]
			else:
				t[j + 1] = t[j + 1] + a[i][j + 1]
		print(t[n - 1], end=' ')
input = sys.stdin.read()
data = list(map(int, input.split()))
n = data[1]
m = data[0]
a = [[0] * n for i in range(m)]
l = data[2:]
k = 0
for i in range(m):
	for j in range(n):
		a[i][j] = l[k]
		k = k + 1
fn(n, m, a)


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


(n, m) = map(int, input().split())
main = [[] for i in range(m)]
for w in range(n):
	li = list(map(int, input().split()))
	for i in range(len(li)):
		main[i].append(li[i])
w = main[0]
ans = [0 for i in range(n)]
ans[0] = w[0]
for i in range(1, n):
	ans[i] = ans[i - 1] + w[i]
for u in range(1, m):
	r = main[u]
	ans[0] = ans[0] + r[0]
	for w in range(1, n):
		if ans[w - 1] > ans[w]:
			ans[w] = ans[w - 1] + r[w]
		else:
			ans[w] = ans[w] + r[w]
print(*ans)


import sys
from functools import lru_cache, cmp_to_key
from heapq import merge, heapify, heappop, heappush
from math import *
from collections import defaultdict as dd, deque, Counter as C
from itertools import combinations as comb, permutations as perm
from bisect import bisect_left as bl, bisect_right as br, bisect
from time import perf_counter
from fractions import Fraction
mod = int(pow(10, 9) + 7)
mod2 = 998244353

def data():
	return sys.stdin.readline().strip()

def out(*var, end='\n'):
	sys.stdout.write(' '.join(map(str, var)) + end)

def l():
	return list(sp())

def sl():
	return list(ssp())

def sp():
	return map(int, data().split())

def ssp():
	return map(str, data().split())

def l1d(n, val=0):
	return [val for i in range(n)]

def l2d(n, m, val=0):
	return [l1d(n, val) for j in range(m)]
(m, n) = l()
A = [l() for i in range(m)]
finish = [0 for i in range(m)]
for i in range(n):
	freeat = 0
	for j in range(m):
		start = max(freeat, finish[j])
		finish[j] = start + A[j][i]
		freeat = finish[j]
print(*finish)


I = lambda : map(int, input().split())
(m, n) = I()
(A, F) = ([list(I()) for _ in range(m)], [0] * m)
for T in zip(*A):
	F[0] += T[0]
	for i in range(1, m):
		F[i] = max(F[i], F[i - 1]) + T[i]
print(*F)


(m, n) = map(int, input().split())
ll = []
for i in range(m):
	ll.append(list(map(int, input().split())))
for j in range(n):
	for i in range(m):
		ll[i][j] += max(0 if i == 0 else ll[i - 1][j], 0 if j == 0 else ll[i][j - 1])
list(map(lambda l: print(l[-1], end=' '), ll))


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


vals = [int(x) for x in input().split()]
m = vals[0]
n = vals[1]
paintersTime = []
for _ in range(m):
	paintersTime.append([int(x) for x in input().split()])
paintersFinishTime = [0] * n
finishTimes = []
for i in range(m):
	for j in range(n):
		painterFinishTime = 0
		if j == 0:
			painterFinishTime = paintersFinishTime[j] + paintersTime[i][j]
		else:
			painterFinishTime = max(paintersFinishTime[j - 1], paintersFinishTime[j]) + paintersTime[i][j]
		paintersFinishTime[j] = painterFinishTime
	finishTimes.append(paintersFinishTime[n - 1])
print(' '.join([str(x) for x in finishTimes]))


(m, n) = map(int, input().split())
L = []
for i in range(m):
	l = list(map(int, input().split()))
	L.append(l)
ans = [0 for i in range(m)]
for i in range(n):
	free = 0
	for j in range(m):
		start = max(free, ans[j])
		ans[j] = start + L[j][i]
		free = ans[j]
for i in range(m):
	print(ans[i], end=' ')