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}.

Difficulty: interview

Starter code:

Solutions:
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 = [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)


# -*- coding: utf-8 -*-

import math
import collections
import bisect
import heapq
import time
import random

"""
created by shhuan at 2017/10/12 23:03

"""

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 = [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])
# print(s)
result = 0
c = 0
for x in s:
    count = 0
    for i in range(n-k+1):
        #print(i)
        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)


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)







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])
# print(s)
result = 0
c = 0
for x in s:
    count = 0
    for i in range(n-k+1):
        #print(i)
        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)

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
    # print(results)
    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
    # calcualte replacements
    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):
    # Go down on col
    # print(f'On col {# col}')
    res, repl = best(col)
    result += res
    replacements += repl
print("{} {}".format(result, replacements))

def best_for_column(matrix, col) -> (int, int):
    """
    Finds the best solution for the given golumn
    :return: The score and the replacement count for this column
    """
    result_by_row = {

    }
    for row in range(n):
        if matrix[row][col] == 1:
            # We're on a 1, start counting rows downwards
            result_by_row[row] = 1
            upper_bound = min(row+k, n)  # either + K or the end (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()))

    # Find the best result and calculate the replacements for this one
    best_result = None
    for row in rows:
        if best_result is None or best_result['result'] < result_by_row[row]:  # always pick the top one for least replacements
            best_result = {'result': result_by_row[row], 'idx': row}
    if best_result is None:
        return 0, 0

    # Calculate the replacements for the best result
    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):
    # Go down on col
    # print(f'On col {# col}')
    res, repl = best_for_column(matrix, col)
    overall_result += res
    overall_replacements += repl
print("{} {}".format(overall_result, overall_replacements))

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)


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

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=list(map(int,input().split()))
l=[]
for i in range(n):
    l.append(list(map(int,input().split())))
l=list(map(list,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)


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())
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 = [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 = list(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)


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=' ')

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)

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


f = lambda: list(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)


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 a, b in zip(t[:n - k], t[k:]):
        p += b - a
        q += a
        if p > x: x, y = p, q
    s += x
    d += y
print(s, d)

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 = [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)