{"raw_statement":[{"iden":"statement","content":"Ivan is playing a strange game.\n\nHe 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:\n\n1.  Initially Ivan's score is 0;\n2.  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;\n3.  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.\n\nOf 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."},{"iden":"input","content":"The first line contains three integer numbers _n_, _m_ and _k_ (1 ≤ _k_ ≤ _n_ ≤ 100, 1 ≤ _m_ ≤ 100).\n\nThen _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."},{"iden":"output","content":"Print two numbers: the maximum possible score Ivan can get and the minimum number of replacements required to get this score."},{"iden":"examples","content":"Input\n\n4 3 2\n0 1 0\n1 0 1\n0 1 0\n1 1 1\n\nOutput\n\n4 1\n\nInput\n\n3 2 1\n1 0\n0 1\n0 0\n\nOutput\n\n2 0"},{"iden":"note","content":"In the first example Ivan will replace the element _a_1, 2."}],"translated_statement":[{"iden":"statement","content":"Ivan 正在玩一个奇怪的游戏。\n\n他有一个包含 #cf_span[n] 行和 #cf_span[m] 列的矩阵 #cf_span[a]。矩阵的每个元素均为 #cf_span[0] 或 #cf_span[1]。行和列均为 #cf_span[1]-索引。Ivan 可以将矩阵中的任意数量的 1 替换为 0。之后，他的游戏得分将按如下方式计算：\n\n显然，Ivan 希望最大化他的得分。同时，他不想更改太多元素，因此他会替换尽可能少的 1 为 0。请帮助他确定他能得到的最大可能得分，以及达到该得分所需的最少替换次数。\n\n第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 100]，#cf_span[1 ≤ m ≤ 100]）。\n\n接下来 #cf_span[n] 行，第 #cf_span[i] 行包含 #cf_span[m] 个整数——矩阵 #cf_span[a] 的第 #cf_span[i] 行的元素。每个数均为 #cf_span[0] 或 #cf_span[1]。\n\n请输出两个数：Ivan 能获得的最大可能得分，以及达到该得分所需的最少替换次数。\n\n在第一个例子中，Ivan 将替换元素 #cf_span[a1, 2]。\n\n"},{"iden":"input","content":"第一行包含三个整数 #cf_span[n]、#cf_span[m] 和 #cf_span[k]（#cf_span[1 ≤ k ≤ n ≤ 100]，#cf_span[1 ≤ m ≤ 100]）。接下来 #cf_span[n] 行，第 #cf_span[i] 行包含 #cf_span[m] 个整数——矩阵 #cf_span[a] 的第 #cf_span[i] 行的元素。每个数均为 #cf_span[0] 或 #cf_span[1]。"},{"iden":"output","content":"请输出两个数：Ivan 能获得的最大可能得分，以及达到该得分所需的最少替换次数。"},{"iden":"examples","content":"输入\n4 3 2\n0 1 0\n1 0 1\n0 1 0\n1 1 1\n输出\n4 1\n\n输入\n3 2 1\n1 0\n0 1\n0 0\n输出\n2 0"},{"iden":"note","content":"在第一个例子中，Ivan 将替换元素 #cf_span[a1, 2]。"}],"sample_group":[],"show_order":[],"formal_statement":"**Definitions**  \nLet $ n, m, k \\in \\mathbb{Z}^+ $ with $ 1 \\leq k \\leq n \\leq 100 $, $ 1 \\leq m \\leq 100 $.  \nLet $ A = (a_{i,j}) \\in \\{0,1\\}^{n \\times m} $ be the given binary matrix.  \n\nLet $ R \\subseteq \\{1, \\dots, n\\} $ be a set of exactly $ k $ rows selected to contribute to the score.  \nLet $ S(R) = \\sum_{j=1}^m \\max_{i \\in R} a_{i,j} $ be the score for row set $ R $.  \nLet $ C(R) = \\sum_{i \\in R} \\sum_{j=1}^m (1 - a_{i,j}) $ be the number of replacements needed to turn all $ 0 $s in rows $ R $ to $ 1 $s (so that the max per column is achieved).  \nLet $ T(R) = \\sum_{i \\notin R} \\sum_{j=1}^m a_{i,j} $ be the number of $ 1 $s outside $ R $ that must be replaced with $ 0 $s.  \n\n**Constraints**  \n1. $ |R| = k $  \n2. Only $ 1 \\to 0 $ replacements are allowed.  \n\n**Objective**  \nMaximize $ S(R) $, and among all $ R $ achieving maximum $ S(R) $, minimize total replacements:  \n$$\n\\text{Minimize } C(R) + T(R)\n$$","simple_statement":null,"has_page_source":false}