题目描述

现在小明有一个 $N\times M$ 格的方格纸，第 $(i,j)$ 个格子上有 $A_{i,j}$ 层的「贴纸」。

小明想要把「贴纸」清除，他可以一次清除某一格上所有层的「贴纸」，但每清除一次就要消耗 $1$ 点「法力」，每清除 $k$ 层「贴纸」可以恢复 $1$ 点「法力」，当小明没有「法力」时，他就不能清除「贴纸」了。

小明现在有 $t$ 点「法力」，请你求出他最多可以清除多少层「贴纸」。

输入格式

输入共 $N+1$ 行。

第 $1$ 行 $4$ 个整数，分别表示方格纸的长度 $N$、宽度 $M$ 以及恢复「法力」所需清除「贴纸」的层量 $k$ 和小明初始时拥有「法力」的点数 $t$。

第 $2$ 至 $N+1$ 行，每行 $M$ 个整数，分别表示该格子上的「贴纸」的层数 $A_{i,j}$。

输出格式

输出共 $1$ 行 $1$ 个整数，表示可以清除「贴纸」层数的最大值。

样例

3 3 5 1
1 2 3
4 5 6
7 8 9

45

样例说明

样例 1 解释

初始时共 $1$ 点「法力」。

以上剩余「法力」点数、清除「贴纸」层数和共计清除「贴纸」层数均指操作后。

综上，可以清除方格纸上所有的「贴纸」，故为 $45$。

数据范围

对于 $100\%$ 的数据，$1\le N,M,t\le10^6$，$1\le k\le10^{18}$，$1\le A_{i,j}\le10^9$ 且 $1\le N\times M\le10^6$。

特殊性质：保证 $\bf k=10^{18}$。