题目内容

在一个 $n$ 行$m$列的矩阵中放置一个边长为d的正方形，正方形必须完整落在矩阵内部。正方形左上角的行号可取 $n−d+1$ 种、列号可取 $m−d+1$ 种，因此放置方式总数为$(n−d+1)(m−d+1)$种。

对矩阵中的每个格子定义它的得分：等于覆盖到该格子所在行的放置方式数量乘以覆盖到该格子所在列的放置方式数量。这里一个放置方式（一个完整的正方形）覆盖到某一行，是指它在竖直方向上压住了这一行；覆盖到某一列同理。也就是说，一行的覆盖数是所有能压住这一行的完整正方形（不同左上角位置）的个数，列同理。

请选出得分最高的前 $k$ 个格子（若有并列，按得分从高到低取满 $k$ 个），求出这$k$个格子的得分之和，再除以放置方式总数。题目保证这个比值一定是整数，输出该整数。

输入描述

输入一行，包含四个整数 $n,m,k,d(1≤n,m≤2000,1≤d≤min(n,m),1≤k≤n×m)$，含义如题所述

输出描述

输出一个整数，表示前$k$ 个最高得分之和除以放置方式总数的结果。

样例1

输入

3 3 3 2

输出

8

说明

放置方式共$(3−2+1)×(3−2+1)=4$ 种。覆盖到第$0,1,2$ 行的放置方式数分别为 $2,4,2$，各列同理为 $2,4,2$。于是九个格子的得分矩阵为$[[4,8,4],[8,16,8],[4,8,4]]$。取最高的$3$个得分 $16,8,8$，和为 $32$，再除以放置方式数 $4$ 得 $8$。

样例2

输入

3 3 9 2

输出

16

说明

取全部$9$ 个格子，得分之和为$4+8+4+8+16+8+4+8+4=64$，除以放置方式数 $4$ 得 $16$