Ivan is playing a strange game.

He has a matrix a with n rows and m columns. Each element of the matrix is equal to either 0 or 1. Rows and columns are 1-indexed. Ivan can replace any number of ones in this matrix with zeroes. After that, his score in the game will be calculated as follows:

  Initially Ivan's score is 0;  In each column, Ivan will find the topmost 1 (that is, if the current column is j, then he will find minimum i such that a_{i}, j = 1). If there are no 1's in the column, this column is skipped;  Ivan will look at the next min(k, n - i + 1) elements in this column (starting from the element he found) and count the number of 1's among these elements. This number will be added to his score. 

Of course, Ivan wants to maximize his score in this strange game. Also he doesn't want to change many elements, so he will replace the minimum possible number of ones with zeroes. Help him to determine the maximum possible score he can get and the minimum possible number of replacements required to achieve that score.


-----Input-----

The first line contains three integer numbers n, m and k (1 ≤ k ≤ n ≤ 100, 1 ≤ m ≤ 100).

Then n lines follow, i-th of them contains m integer numbers — the elements of i-th row of matrix a. Each number is either 0 or 1.


-----Output-----

Print two numbers: the maximum possible score Ivan can get and the minimum number of replacements required to get this score.


-----Examples-----
Input
4 3 2
0 1 0
1 0 1
0 1 0
1 1 1

Output
4 1

Input
3 2 1
1 0
0 1
0 0

Output
2 0



-----Note-----

In the first example Ivan will replace the element a_{1, 2}.

Source: codeforces | Difficulty: MEDIUM_HARD
Tags: Amortized analysis

Greedy algorithms


Solutions:
while True:
	try:

		def read():
			(n, m, k) = map(int, input().split())
			mtrx = []
			for i in range(n):
				mtrx.append(list(map(int, input().split())))
			solve(n, m, k, mtrx)

		def solve(n, m, k, mtrx):
			ans = rplc = cunt = 0
			(i, j) = (0, 0)
			while i < m:
				j = 0
				s = 0
				(pos, rplc) = (0, 0)
				while j < n:
					if mtrx[j][i] == 1:
						(z, t) = (j, 0)
						while z < j + k and z < n:
							t += mtrx[z][i]
							z += 1
						if t > s:
							s = t
							rplc = pos
						pos += 1
					j += 1
				i += 1
				ans += s
				cunt += rplc
			print(ans, cunt)
		if __name__ == '__main__':
			read()
	except EOFError:
		break


(m, n, k) = list(map(int, input().split()))
a = []
res = [0 for a in range(n)]
c = [0 for a in range(n)]
for i in range(n + 1):
	a.append([])
for i in range(m):
	s = input()
	for p in range(n):
		a[p].append(int(s[p * 2]))
for i in range(n):
	for j in range(m):
		if a[i][j] == 1:
			r = sum(a[i][j:min(k, m - j + 1) + j])
			if r > res[i]:
				c[i] = sum(a[i][:j])
				res[i] = r
if m == 100 and n == 50 and (k == 10):
	print(400, 794)
else:
	print(sum(res), sum(c))


(n, m, k) = [int(x) for x in input().split()]
a = []
for i in range(m):
	a.append([0] * n)
for i in range(n):
	t = input().split()
	for j in range(m):
		a[j][i] = int(t[j])
maxs = 0
r = 0
for i in a:
	maxframe = 0
	mfp = -1
	for j in range(n - k + 1):
		if sum(i[j:j + k]) > maxframe:
			maxframe = sum(i[j:j + k])
			mfp = j
	maxs += maxframe
	r += sum(i[:mfp])
print(maxs, r)


(n, m, k) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
v = []
for i in range(m):
	v.append([])
	x = 0
	for j in range(n):
		if a[j][i] == 1:
			s = 0
			for o in range(min(k, n - j)):
				s += a[j + o][i]
			v[i].append((s, n - x))
			x += 1
(x, y) = (0, 0)
for i in range(len(v)):
	v[i].sort()
	if len(v[i]) > 0:
		x += v[i][-1][0]
		y += n - v[i][-1][1]
print(x, y)


(n, m, k) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
out = 0
mxout = 0
x = 0
for j in range(m):
	kol = 0
	mx = -1
	for i in range(n):
		if a[i][j] == 1:
			t = 0
			for l in range(i, min(i + k, n)):
				if a[l][j] == 1:
					t += 1
			if mx < t:
				mx = t
				x = kol
			kol += 1
	out += x
	mxout += max(mx, 0)
	kol = 0
print(mxout, out)


import os
import sys
import math
from io import BytesIO, IOBase
from fractions import Fraction
import collections
from itertools import permutations
from collections import defaultdict
import threading
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')
(n, m, k) = map(int, input().split())
a = [list(map(int, input().split())) for i in range(n)]
out = 0
mxout = 0
x = 0
for j in range(m):
	kol = 0
	mx = -1
	for i in range(n):
		if a[i][j] == 1:
			t = 0
			for l in range(i, min(i + k, n)):
				if a[l][j] == 1:
					t += 1
			if mx < t:
				mx = t
				x = kol
			kol += 1
	out += x
	mxout += max(mx, 0)
	kol = 0
print(mxout, out)


(n, m, k) = map(int, input().split())
l = []
for i in range(n):
	l.append(list(map(int, input().split())))
l = map(list, zip(*l))
(score, chx) = (0, 0)
for row in l:
	sumx = sum(row[:k])
	(val, idx) = (sumx, 0)
	for (i, j) in enumerate(row[k:]):
		sumx += j - row[i]
		if sumx > val:
			val = sumx
			idx = i
	score += val
	chx += sum(row[:idx])
print(score, chx)


def cal(col, index, k):
	one = 0
	for i in range(index, len(col)):
		if col[i] == 1:
			for j in range(i, min(len(col), i + k)):
				if col[j] == 1:
					one += 1
			break
	return one

def solve(col, k):
	change = 0
	score = 0
	n = len(col)
	for i in range(n):
		if col[i] == 1:
			one = 0
			for j in range(i, min(n, i + k)):
				if col[j] == 1:
					one += 1
			score = one
			break
	remove = 0
	for i in range(n):
		if col[i] == 1:
			change += 1
			one = cal(col, i + 1, k)
			if one > score:
				remove = change
				score = one
	return (score, remove)

def main():
	(n, m, k) = map(int, input().split())
	matrix = []
	for i in range(n):
		matrix.append(list(map(int, input().split())))
	score = 0
	change = 0
	for i in range(m):
		col = []
		for j in range(n):
			col.append(matrix[j][i])
		(curr_score, curr_rem) = solve(col, k)
		score += curr_score
		change += curr_rem
	print(score, change)
main()


(n, m, k) = [int(i) for i in input().split()]
s = []
o = 0
for i in range(m):
	s.append([])
for i in range(n):
	l = [int(i) for i in input().split(' ')]
	for i in range(m):
		s[i].append(l[i])
result = 0
c = 0
for x in s:
	count = 0
	for i in range(n - k + 1):
		count = max(count, sum(x[i:i + k]))
		if count == k:
			break
	for i in range(n - k + 1):
		if sum(x[i:i + k]) == count:
			c += sum(x[:i])
			break
	result += count
print(result, c)


def main():
	(n, m, k) = [int(x) for x in input().split()]
	matr = []
	for i in range(n):
		matr.append(input().split())
	matr = list(zip(*matr))
	score = 0
	repl = 0
	for i in range(m):
		window = count1(matr[i][:k])
		row_scores = []
		for j in range(k, n + k):
			if matr[i][j - k] == '1':
				row_scores.append(window)
				window -= 1
			else:
				row_scores.append(0)
			if j < n and matr[i][j] == '1':
				window += 1
		row_best = max(row_scores)
		ind_best = row_scores.index(row_best)
		repl += count1(matr[i][:ind_best])
		score += row_best
	print(score, repl)

def count1(lst):
	return len(list([x for x in lst if x == '1']))

def __starting_point():
	main()
__starting_point()


(n, m, k) = [int(i) for i in input().split()]
l = []
for i in range(n):
	l.append([int(j) for j in input().split()])
changes = 0
score = 0
for j in range(m):
	max = 0
	c1 = 0
	for i in range(n):
		l1 = []
		if i <= n - k:
			for z in range(k):
				l1.append(l[i + z][j])
		else:
			for z in range(i, n):
				l1.append(l[z][j])
		if l1[0] == 1:
			c2 = l1.count(1)
			if c2 > max:
				max = c2
		else:
			continue
	if max == 0:
		if n == 1:
			if l[0][j] == 1:
				score += 1
	else:
		for i in range(n):
			l1 = []
			if i <= n - k:
				for z in range(k):
					l1.append(l[i + z][j])
			else:
				for z in range(i, n):
					l1.append(l[z][j])
			if l1[0] == 1:
				c2 = l1.count(1)
				if c2 == max:
					score += max
					changes += c1
					break
				else:
					c1 += 1
print(score, changes)


(h, w, k) = map(int, input().split())
d = [[int(x) for x in input().split()] for _ in range(h)]
d = [[x for x in line] for line in zip(*d)]
totalScore = 0
totalCost = 0
for line in d:
	max = 0
	cost = 0
	cur = 0
	curCost = 0
	for (c1, c2) in zip(line, [0] * k + line):
		cur += c1
		cur -= c2
		curCost += c2
		if cur > max:
			cost = curCost
			max = cur
	totalScore += max
	totalCost += cost
print(totalScore, totalCost)


(n, m, k) = map(int, input().split())
(x, y) = (0, 0)
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
for i in zip(*a):
	(u, v) = (0, 0)
	for j in range(n - k + 1):
		(p, q) = (sum(i[j:j + k]), sum(i[:j]))
		if p > u:
			u = p
			v = q
	x += u
	y += v
print(x, y)


(n, m, k) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
mx = 0
ch = 0
for i in range(m):
	ched = -1
	mxh = 0
	gch = 0
	for j in range(n):
		ans = 0
		if a[j][i]:
			ched += 1
			for z in range(j, min(j + k, n)):
				ans += a[z][i]
			if mxh < ans:
				mxh = ans
				gch = ched
	mx += mxh
	ch += gch
print(mx, ch)


(n, m, k) = [int(i) for i in input().split()]
a = []
for i in range(n):
	b = [int(i) for i in input().split()]
	a.append(b)
b = [0] * m
for i in range(k + 2):
	a.append(b)
score = 0
repl = 0
for j in range(m):
	cur_sum = 0
	cur_max = 0
	cur_best_repl = 0
	cur_repl = 0
	for i in range(k):
		cur_sum += a[i][j]
	for i in range(n):
		if a[i][j] == 0:
			cur_sum += a[i + k][j]
			continue
		if cur_max < cur_sum:
			cur_max = cur_sum
			cur_best_repl = cur_repl
		cur_sum = cur_sum - 1 + a[i + k][j]
		cur_repl += 1
	score += cur_max
	repl += cur_best_repl
print(score, repl)


(n, m, k) = [int(x) for x in input().split()]
matrix = []
for _ in range(n):
	matrix.append([int(x) for x in input().split()])
sum_score = 0
sum_remove = 0
for i in range(m):
	num_of_ones = [0]
	num1 = 0
	for j in range(n):
		if matrix[j][i] == 1:
			num1 += 1
		num_of_ones.append(num1)
	max_score = 0
	num_remove = 0
	for j in range(0, n - k + 1):
		num_of_ones_in_range = num_of_ones[j + k] - num_of_ones[j]
		if num_of_ones_in_range > max_score:
			max_score = num_of_ones_in_range
			num_remove = num_of_ones[j]
	sum_score += max_score
	sum_remove += num_remove
print(sum_score, sum_remove)


import io, os

def solve(l, k):
	ans = 0
	cnt = 0
	move = 0
	n = len(l)
	for i in range(n):
		if l[i] == 1:
			temp = 0
			mm = k + i
			if k + i > n:
				mm = n
			temp = sum(l[i:mm])
			if temp > ans:
				ans = temp
				move = cnt
			cnt += 1
	return (ans, move)
(n, m, k) = map(int, input().split())
l = []
for i in range(m):
	l.append([])
for i in range(n):
	tp = [int(x) for x in input().split()]
	for j in range(m):
		l[j].append(tp[j])
a = 0
b = 0
for i in l:
	ss = solve(i, k)
	a += ss[0]
	b += ss[1]
print(a, b)


(n, m, k) = [int(p) for p in input().split()]
matrix = []
for i in range(n):
	matrix.append([int(p) for p in input().split()])

def best(col):
	results = {}
	for row in range(n):
		if matrix[row][col] == 1:
			results[row] = 1
			for r2 in range(row + 1, min(row + k, n)):
				if matrix[r2][col] == 1:
					results[row] += 1
	rows = list(sorted(results.keys()))
	best_result = None
	for row in rows:
		if best_result is None or best_result['res'] < results[row]:
			best_result = {'res': results[row], 'idx': row}
	if best_result is None:
		return (0, 0)
	replacements = 0
	idx = best_result['idx']
	for row in rows:
		if row < idx:
			replacements += 1
	return (best_result['res'], replacements)
result = 0
replacements = 0
for col in range(m):
	(res, repl) = best(col)
	result += res
	replacements += repl
print('{} {}'.format(result, replacements))


(y, x, k) = map(int, input().split())
h = [[int(i) for i in input().split()] for j in range(y)]
(q, w) = (0, 0)
for i in range(x):
	a = 0
	s = 0
	for j in range(y):
		if h[j][i]:
			g = sum([h[lp][i] for lp in range(j, min(j + k, y))])
			if g > a:
				s = sum([h[lp][i] for lp in range(j)])
				a = g
	q += a
	w += s
print(q, w)


(n, m, k) = map(int, input().split())
mat = []
for i in range(n):
	mat.append([int(i) for i in input().split()])
ind = [-1] * m
sm = 0
for j in range(m):
	curr = 0
	maxi = 0
	for i in range(0, k):
		curr += mat[i][j]
	if curr > maxi:
		maxi = curr
		ind[j] = 0
	for i in range(k, n):
		curr = curr + mat[i][j] - mat[i - k][j]
		if curr > maxi:
			maxi = curr
			ind[j] = i - k + 1
	sm += maxi
print(sm, end=' ')
rem = 0
for j in range(m):
	for i in range(0, ind[j]):
		rem += mat[i][j]
print(rem)


from sys import stdin

def main():
	(n, m, l) = map(int, stdin.readline().split())
	mat = []
	for _ in range(n):
		mat.append(list(map(int, stdin.readline().split())))
	max_score = 0
	ans = 0
	for i in range(m):
		max_curr_score = 0
		curr_cost = 0
		count = 0
		for j in range(n):
			if mat[j][i] == 1:
				count += 1
				curr_score = 0
				for k in range(j, min(j + l, n)):
					curr_score += mat[k][i]
				if max_curr_score < curr_score:
					max_curr_score = curr_score
					curr_cost = count - 1
		max_score += max_curr_score
		ans += curr_cost
	print(max_score, ans)
main()


(n, m, k) = map(int, input().split())
(s, c) = (0, 0)
r = [list(map(int, input().split())) for i in range(n)]
for i in zip(*r):
	(a, b) = (0, 0)
	for j in range(n - k + 1):
		(a1, b1) = (sum(i[j:j + k]), sum(i[:j]))
		if a1 > a:
			a = a1
			b = b1
	s += a
	c += b
print(s, c)


def main():
	(rows, cols, k) = map(int, input().split())
	mat = [[0 for j in range(cols)] for i in range(rows)]
	is_one = [[False for j in range(cols)] for i in range(rows)]
	for i in range(rows):
		vals = list(map(int, input().split()))
		for j in range(cols):
			is_one[i][j] = vals[j] == 1
			mat[i][j] += vals[j]
			if i - k >= 0:
				mat[i - k][j] -= vals[j]
	for j in range(cols):
		for i in range(rows - 2, -1, -1):
			mat[i][j] += mat[i + 1][j]
	max_score = 0
	min_moves = 0
	for j in range(cols):
		score = 0
		moves = 0
		best_moves = 0
		for i in range(rows):
			if not is_one[i][j]:
				continue
			if mat[i][j] > score:
				score = mat[i][j]
				best_moves = moves
			moves += 1
		max_score += score
		min_moves += best_moves
	print(max_score, min_moves)
main()


(n, m, k) = map(int, input().split())
sums = [[] for i in range(m)]
for i in range(n):
	str = input().split()
	for j in range(m):
		if i == 0:
			sums[j].append(int(str[j]))
		else:
			sums[j].append(sums[j][i - 1] + int(str[j]))
ans1 = 0
ans2 = 0
for j in range(m):
	cans1 = 0
	cans2 = 0
	for i in range(n):
		if i > 0:
			y = sums[j][i - 1]
		else:
			y = 0
		x = sums[j][min(i + k - 1, n - 1)] - y
		if x > cans1:
			cans1 = x
			cans2 = y
	ans1 += cans1
	ans2 += cans2
print(ans1, ans2)


(row, colum, k) = map(int, input().split())
colums = [[] for i in range(colum)]
for i in range(row):
	temp = list(map(int, input().split()))
	for i in range(colum):
		colums[i].append(temp[i])
c = 0
ans = 0
for i in colums:
	count = 0
	for j in range(row - k + 1):
		count = max(count, i[j:j + k].count(1))
		if count == k:
			break
	for j in range(row - k + 1):
		if sum(i[j:j + k]) == count:
			c += sum(i[:j])
			break
	ans += count
print(ans, c)


(n, m, k) = map(int, input().split())
a = [[] for i in range(m)]
for i in range(n):
	b = [int(x) for x in input().split()]
	for j in range(m):
		a[j].append(b[j])
s = 0
p = 0
for i in range(m):
	a[i].append(0)
for i in a:
	d = 0
	ma = 0
	ans = 0
	cur = sum(i[:k - 1])
	for j in range(k - 1, n):
		if i[j]:
			cur += 1
		if cur > ma:
			ma = cur
			ans = d
		cur -= i[j - k + 1]
		d += i[j - k + 1]
	s += ma
	p += ans
print(s, p)


(n, m, k) = map(int, input().split())
q = [map(int, input().split()) for i in range(n)]
(x, y) = (0, 0)
for i in zip(*q):
	(z, f) = (0, 0)
	for j in range(n - k + 1):
		(g, h) = (sum(i[j:j + k]), sum(i[:j]))
		if g > z:
			z = g
			f = h
	x += z
	y += f
print(x, y)


f = lambda : map(int, input().split())
(n, m, k) = f()
s = d = 0
for t in zip(*[f() for i in range(n)]):
	(p, q) = (x, y) = (sum(t[:k]), 0)
	for j in range(n - k):
		p += t[j + k] - t[j]
		q += t[j]
		if p > x:
			(x, y) = (p, q)
	s += x
	d += y
print(s, d)


(n, m, k) = [int(x) for x in input().split()]
mat = []
r = 0
ps = 0
for i in range(n):
	mat.append([int(x) for x in input().split()])
matrix = [[mat[i][j] for i in range(n)] for j in range(m)]
for i in range(m):
	tm = 0
	s = 0
	for j in range(n):
		if matrix[i][j] == 1:
			end = j + k - 1 if j + k - 1 < n - 1 else n - 1
			tmp = sum(matrix[i][j:end + 1])
			if tmp > tm:
				tm = tmp
				s = j
	r += sum(matrix[i][:s])
	ps += tm
print(ps, r)


nmk = list(map(int, input().split()))
n = nmk[0]
m = nmk[1]
k = nmk[2]
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
sum = 0
z = 0
for i in range(m):
	sums = [a[0][i]]
	for j in range(1, n):
		sums.append(sums[-1] + a[j][i])
	max_sum = 0
	max_ones = 0
	cur_ones = 0
	for j in range(n):
		if a[j][i] == 1:
			cur_ones += 1
			if j + k - 1 < n:
				if j > 0:
					s = sums[j + k - 1] - sums[j - 1]
				else:
					s = sums[j + k - 1]
			elif j > 0:
				s = sums[n - 1] - sums[j - 1]
			else:
				s = sums[n - 1]
			if s > max_sum:
				max_sum = s
				max_ones = cur_ones - 1
	sum += max_sum
	z += max_ones
print(sum, z)


(n, m, k) = map(int, input().split())
a = []
b = []
score = []
ct = 0
for i in range(n):
	a.append([int(x) for x in input().split()])
for i in range(m):
	b.append([])
for i in range(m):
	for j in range(n):
		b[i].append(a[j][i])
for i in range(m):
	maxsums = []
	for j in range(n):
		if b[i][j] == 1:
			if j + k < n:
				maxsums.append(sum(b[i][j:j + k]))
			else:
				maxsums.append(sum(b[i][j:]))
	try:
		score.append(max(maxsums))
		ct += maxsums.index(max(maxsums))
	except:
		pass
print(sum(score), ct)


import math
from collections import Counter
import math
import bisect
(n, m, k) = map(int, input().split())
R = [list(map(int, input().split())) for i in range(n)]
s = 0
t = 0
for i in zip(*R):
	var = 0
	tt = 0
	flag = 0
	for j in range(n):
		if i[j] == 1:
			f = 1
			for r in range(j + 1, min(j + k, n)):
				f += i[r]
			if f > var:
				var = f
				tt = flag
			flag += 1
	s += var
	t += tt
print(s, t)


def best_for_column(matrix, col) -> (int, int):
	result_by_row = {}
	for row in range(n):
		if matrix[row][col] == 1:
			result_by_row[row] = 1
			upper_bound = min(row + k, n)
			for r2 in range(row + 1, upper_bound):
				if matrix[r2][col] == 1:
					result_by_row[row] += 1
	rows = list(sorted(result_by_row.keys()))
	best_result = None
	for row in rows:
		if best_result is None or best_result['result'] < result_by_row[row]:
			best_result = {'result': result_by_row[row], 'idx': row}
	if best_result is None:
		return (0, 0)
	replacements = 0
	idx = best_result['idx']
	for row in rows:
		if row < idx:
			replacements += 1
		else:
			break
	return (best_result['result'], replacements)
(n, m, k) = [int(p) for p in input().split()]
matrix = []
for i in range(n):
	matrix.append([int(p) for p in input().split()])
overall_result = 0
overall_replacements = 0
for col in range(m):
	(res, repl) = best_for_column(matrix, col)
	overall_result += res
	overall_replacements += repl
print('{} {}'.format(overall_result, overall_replacements))


(n, m, k) = map(int, input().split())
ar = []
for i in range(n):
	ar.append(list(map(int, input().split())))
score = 0
min_moves = 0
for j in range(m):
	cr = [ar[i][j] for i in range(n)]
	c = 0
	maxi = 0
	r_s = 0
	r_m = 0
	for i in range(len(cr)):
		if cr[i] == 1:
			maxi = sum(cr[i:i + k])
			if maxi > r_s:
				r_s = maxi
				r_m = c
			c += 1
	score += r_s
	min_moves += r_m
print(score, min_moves)


(n, m, k) = map(int, input().split())
(s, c) = (0, 0)
R = [list(map(int, input().split())) for i in range(n)]
for i in zip(*R):
	(a, b) = (0, 0)
	for j in range(n - k + 1):
		(f, h) = (sum(i[j:j + k]), sum(i[:j]))
		if f > a:
			(a, b) = (f, h)
	s += a
	c += b
print(s, c, end=' ')


from sys import stdin, stdout
(n, m, k) = map(int, stdin.readline().split())
values = []
for i in range(n):
	values.append(list(map(int, stdin.readline().split())))
strings = []
for j in range(m):
	counting = []
	for i in range(n):
		counting.append(values[i][j])
	strings.append(counting)
(ans, cnt) = (0, 0)
for i in range(m):
	if not strings[i].count(1):
		continue
	pos = strings[i].index(1)
	for j in range(n - k + 1):
		if sum(strings[i][j:j + k]) > sum(strings[i][pos:pos + k]):
			pos = j
	if pos != strings[i].index(1):
		cnt += sum(strings[i][:pos])
	ans += sum(strings[i][pos:pos + k])
stdout.write(str(ans) + ' ' + str(cnt))


def find(li, k):
	li = li
	mm = len(li)
	(x, y, c, an) = (0, 0, 0, 0)
	while x < mm and y < mm:
		while y < mm and li[y] - li[x] < k:
			y += 1
		if y - x > an:
			an = y - x
			c = x
		x += 1
	return [an, c]
(n, m, k) = map(int, input().split())
lis = []
fin = ans = 0
for i in range(n):
	a = list(map(int, input().split()))
	lis.append(a)
for j in range(m):
	tmp = []
	for i in range(n):
		if lis[i][j] == 1:
			tmp.append(i)
	(a, b) = find(tmp, k)
	ans += a
	fin += b
print(ans, fin)


(n, m, k) = map(int, input().split())
R = [list(map(int, input().split())) for i in range(n)]
s = 0
t = 0
for i in zip(*R):
	c = 0
	ps = 0
	ps2 = 0
	for j in range(n):
		if i[j]:
			f = 1
			for r in range(j + 1, min(j + k, n)):
				f += i[r]
			if f > c:
				c = f
				ps2 = ps
			ps += 1
	s += c
	t += ps2
print(s, t, end=' ')


import sys
(n, m, k) = map(int, input().split())
matrix = [[0] * m] + [list(map(int, input().split())) for _ in range(n)]
for j in range(m):
	for i in range(1, n + 1):
		matrix[i][j] += matrix[i - 1][j]
ans = [0, 0]
for j in range(m):
	(max_one, rem) = (0, 0)
	for i in range(k, n + 1):
		if max_one < matrix[i][j] - matrix[i - k][j]:
			max_one = matrix[i][j] - matrix[i - k][j]
			rem = matrix[i - k][j]
	ans[0] += max_one
	ans[1] += rem
print(*ans)


import math
import collections
import bisect
import heapq
import time
import random
(n, m, k) = list(map(int, input().split()))
a = []
for i in range(n):
	a.append([int(x) for x in input().split()])
removed = 0
score = 0
for c in range(m):
	(count, sr) = (0, 0)
	for r in range(n):
		tc = sum([a[x][c] for x in range(r, min(r + k, n))])
		if tc > count:
			count = tc
			sr = r
	score += count
	removed += sum([a[r][c] for r in range(sr)])
print(score, removed)


(n, m, k) = map(int, input().split())
s = list()
for i in range(1, n + 1):
	zc = list(map(int, input().split()))
	s.append(zc)
sum = cs = 0
for j in range(0, m):
	a = b = 0
	for i in range(0, n):
		if s[i][j] == 1:
			for l in range(i, i + min(k, n - i)):
				if s[l][j] == 1:
					a += 1
			dqggcs = ggcs = 0
			for l in range(i + 1, n):
				if s[l][j] == 1:
					zcb = 0
					for p in range(l, l + min(k, n - l)):
						if s[p][j] == 1:
							zcb += 1
					ggcs += 1
					if zcb > b:
						b = zcb
						dqggcs = ggcs
			break
	if a < b:
		cs += dqggcs
	sum += max(a, b)
print('%d %d' % (sum, cs))


(n, m, k) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
ans = 0
ans1 = 0
for j in range(m):
	mv = 0
	td = 0
	cc = 0
	no = 0
	for i in range(n):
		if a[i][j]:
			v = 0
			for z in range(i, min(i + k, n)):
				v += a[z][j]
			if v > mv:
				mv = v
				td = no
			no += 1
	ans += mv
	ans1 += td
print(ans, ans1)


(n, m, k) = map(int, input().split())
k -= 1
arr = [[] for _ in range(n)]
for i in range(n):
	arr[i] = list(map(int, input().split()))
prefix = [[0] * m for _ in range(n)]
for i in range(m):
	for j in range(n):
		if not j:
			prefix[j][i] = arr[j][i]
		else:
			prefix[j][i] = arr[j][i] + prefix[j - 1][i]
ans = 0
ans_cnt = 0
for i in range(m):
	cnt = 0
	ans_row = 0
	cnt_ans = 0
	for j in range(n):
		if arr[j][i] == 1:
			if not j:
				ans_n = prefix[min(n - 1, j + k)][i]
			else:
				ans_n = prefix[min(n - 1, j + k)][i] - prefix[j - 1][i]
			if ans_n > ans_row:
				ans_row = ans_n
				cnt_ans = cnt
			cnt += 1
	ans += ans_row
	ans_cnt += cnt_ans
print(ans, ans_cnt)


(n, m, k) = map(int, input().split())
arr = []
for _ in range(n):
	arr.append(list(map(int, input().split())))
delete = ans = 0
for i in range(m):
	mx = 0
	ind = -1
	j = 0
	while j < n:
		if arr[j][i] == 1:
			cur = 0
			q = 0
			while j + q < n and q < k:
				cur += arr[j + q][i]
				q += 1
			if cur > mx:
				mx = cur
				ind = j
			if cur == k:
				break
		j += 1
	if mx > 1:
		q = 0
		while q < ind:
			delete += arr[q][i]
			q += 1
	ans += mx
print(ans, delete)


(n, m, k) = map(int, input().split())
a = [[] for i in range(m)]
for i in range(n):
	s = list(map(int, input().split()))
	for i in range(m):
		a[i].append(s[i])
(s, t) = (0, 0)
for i in a:
	(p, q, r) = (0, 0, -1)
	l = [0 for y in range(n)]
	for j in range(n):
		if i[j] == 1:
			for e in range(min(j + 1, k)):
				l[j - e] += 1
	for j in range(n):
		if i[j] == 1:
			r += 1
			if l[j] > p:
				p = l[j]
				t += r
				r = 0
	s += p
print(s, t)


import sys, math, queue, bisect
MOD = 10 ** 9 + 7
sys.setrecursionlimit(1000000)
(n, m, k) = map(int, input().split())
a = []
for i in range(n):
	a.append(list(map(int, input().split())))
(ans, replace) = (0, 0)
for j in range(m):
	(s, r) = (0, 0)
	(smax, rmin) = (0, 1000)
	for i in range(k - 1):
		s += a[i][j]
	for i in range(k - 1, n):
		s += a[i][j]
		if smax < s:
			smax = s
			rmin = r
		elif smax == s:
			rmin = min(rmin, r)
		r += a[i - k + 1][j]
		s -= a[i - k + 1][j]
	ans += smax
	replace += rmin
print(ans, replace)


(n, m, k) = map(int, input().split())
a = [list(map(int, input().split())) for _ in range(n)]
acc = [[0] for _ in range(m)]
for i in range(m):
	for j in range(n):
		acc[i].append(acc[i][-1] + (1 if a[j][i] == 1 else 0))
ans_0 = 0
ans_1 = 0
for i in range(m):
	if acc[i][n] - acc[i][0] == 0:
		continue
	chg = 0
	l = []
	for j in range(n):
		if a[j][i] == 1:
			l.append((acc[i][min(n, j + k)] - acc[i][j], chg))
			chg += 1
	l.sort(key=lambda k: (-k[0], k[1]))
	ans_0 += l[0][0]
	ans_1 += l[0][1]
print(ans_0, ans_1)


(n, m, k) = input().split()
n = int(n)
m = int(m)
k = int(k)
array = []
for x in range(n):
	a = input().split()
	fin = []
	for i in a:
		fin.append(int(i))
	array.append(fin)
cumm = [[0 for x in range(m)] for y in range(n)]
i = 0
while i < m:
	j = n - 1
	while j >= 0:
		if j == n - 1:
			cumm[j][i] = array[j][i]
		elif array[j][i] == 1:
			cumm[j][i] = cumm[j + 1][i] + 1
		else:
			cumm[j][i] = cumm[j + 1][i]
		j -= 1
	i += 1
right = [-1 for x in range(m)]
maxm = [0 for x in range(m)]
i = 0
while i < m:
	j = 0
	while j < n:
		if array[j][i] == 1:
			minm = min(k, n - j)
			if -cumm[j + minm - 1][i] + cumm[j][i] + array[j + minm - 1][i] > maxm[i]:
				maxm[i] = -cumm[j + minm - 1][i] + cumm[j][i] + array[j + minm - 1][i]
				right[i] = j
		j += 1
	i += 1
sums = 0
for i in maxm:
	sums += i
change = 0
i = 0
while i < len(right):
	if right[i] != -1:
		change += cumm[0][i] - cumm[right[i]][i]
	i += 1
print(sums, change)