T427015 「SFOI Round 1」Shade

> つづく日々の道の先を > > 塞ぐ影にアイデアを > > 雨の音で歌を歌おう > > すべて越えて響け > > つづく日々を奏でる人へ > > すべて越えて届け 

小 F 很喜欢[「アイデア」](https://www.bilibili.com/video/BV1X54y1q7g4/)这首歌。 现在小 F 有一个 $N\times M$ 格的方格纸，第 $(i,j)$ 个格子上有 $A_{i,j}$ 层的「影子」。 小 F 想要把「影子」划破，他可以一次清除某一格上所有层的「影子」，但每清除一次就要消耗 $1$ 点「妙意」，每清除 $k$ 层「影子」可以恢复 $1$ 点「妙意」，当小 F 没有「妙意」时，他就不能清除「影子」了。 小 F 现在有 $t$ 点「妙意」，请你求出他最多可以清除多少层「影子」。

输入共 $N+1$ 行。 第 $1$ 行 $4$ 个整数，分别表示方格纸的长度 $N$、宽度 $M$ 以及恢复「妙意」所需清除「影子」的层量 $k$ 和小 F 初始时拥有「妙意」的点数 $t$。 第 $2$ 至 $N+1$ 行，每行 $M$ 个整数，分别表示该格子上的「影子」的层数 $A_{i,j}$。

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

**【样例 1 解释】** 初始时共 $1$ 点「妙意」。 | 操作 | 剩余「妙意」点数 | 清除「影子」层数 | 共计清除「影子」层数 | | :----------: | :----------: | :----------: | :----------: | | 清除 $(3,3)$ | $0$ | $9$ | $9$ | | 恢复「妙意」 | $1$ | $4$ | $9$ | | 清除 $(3,2)$ | $0$ | $12$ | $17$ | | 恢复「妙意」 | $2$ | $2$ | $17$ | | 清除 $(3,1)$ | $1$ | $9$ | $24$ | | 恢复「妙意」 | $2$ | $4$ | $24$ | | 清除 $(2,3)$ | $1$ | $10$ | $30$ | | 恢复「妙意」 | $3$ | $0$ | $30$ | | 清除 $(2,2)$ | $2$ | $5$ | $35$ | | 恢复「妙意」 | $3$ | $0$ | $35$ | | 清除 $(2,1)$ | $2$ | $4$ | $39$ | | 清除 $(1,3)$ | $1$ | $7$ | $42$ | | 恢复「妙意」 | $2$ | $2$ | $42$ | | 清除 $(1,2)$ | $1$ | $4$ | $44$ | | 清除 $(1,1)$ | $0$ | $5$ | $45$ | | 恢复「妙意」 | $1$ | $0$ | $45$ | 以上剩余「妙意」点数、清除「影子」层数和共计清除「影子」层数均指操作后。 综上，可以清除方格纸上所有的「影子」，故为 $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$。 | $\text{Point}$ | $N,M\le$ | $\text{Note}$ | | :----------: | :----------: | :----------: | | $1$ | $10$ | $\text{Yes}$ | | $2$ | $10$ | $\text{No}$ | | $3$ | $200$ | $\text{Yes}$ | | $4$ | $200$ | $\text{No}$ | | $5$ | $10^3$ | $\text{Yes}$ | | $6$ | $10^3$ | $\text{No}$ | | $7\sim8$ | $10^6$ | $\text{Yes}$ | | $9\sim10$ | $10^6$ | $\text{No}$ | - $\text{Note}$：保证 $k=10^{18}$。