噜噜的能量行

题目描述

噜噜得到一个 $n$ 行 $m$ 列的能量矩阵。第 $i$ 行第 $j$ 列的数为 $a_{i,j}$。

他可以进行若干次能量提升操作。每次操作可以选择以下两种方式之一：

• 选择一整行，使这一行的所有数都加 $1$；
• 选择一整列，使这一列的所有数都加 $1$。

对于第 $i$ 行，如果这一行所有数的和大于等于 $S$，则称第 $i$ 行是一个达标能量行。

现在噜噜想知道，至少需要进行多少次操作，才能让矩阵中至少有 $k$ 行成为达标能量行。

输入格式

第一行输入四个整数 $n,m,k,S$，表示矩阵的行数、列数、要求的达标行数和目标能量值。

接下来 $n$ 行，每行 $m$ 个整数，第 $i$ 行第 $j$ 个整数表示 $a_{i,j}$。

输出格式

输出一行一个整数，表示最少需要进行多少次操作。

样例输入 #1

3 4 2 15
1 2 3 4
2 2 2 2
10 1 1 2

样例输出 #1

2

样例说明 #1

原来三行的行和分别为：

10 8 14

可以先选择任意一列加 $1$，此时每一行的行和都会增加 $1$，变为：

11 9 15

然后选择第 $1$ 行加 $1$，第 $1$ 行的行和会增加 $4$，变为：

15 9 15

此时第 $1$ 行和第 $3$ 行都达到了 $15$，一共进行了 $2$ 次操作。

可以证明，进行 $1$ 次操作无法让至少 $2$ 行达标，因此答案为 $2$。

样例输入 #2

2 3 2 6
1 2 3
4 5 6

样例输出 #2

0

样例输入 #3

4 2 3 8
1 1
2 1
3 1
4 1

样例输出 #3

5

数据范围

对于 $100\%$ 的数据，保证：

• $1\le n,m\le 100$；
• $1\le k\le n$；
• $1\le S\le 10^4$；
• $0\le a_{i,j}\le 10^4$。