CF912D.Fishes

While Grisha was celebrating New Year with Ded Moroz, Misha gifted Sasha a small rectangular pond of size n × m, divided into cells of size 1 × 1, inhabited by tiny evil fishes (no more than one fish per cell, otherwise they'll strife!).

The gift bundle also includes a square scoop of size r × r, designed for fishing. If the lower-left corner of the scoop-net is located at cell (x, y), all fishes inside the square (x, y)...(x + r - 1, y + r - 1) get caught. Note that the scoop-net should lie completely inside the pond when used.

Unfortunately, Sasha is not that skilled in fishing and hence throws the scoop randomly. In order to not frustrate Sasha, Misha decided to release k fishes into the empty pond in such a way that the expected value of the number of caught fishes is as high as possible. Help Misha! In other words, put k fishes in the pond into distinct cells in such a way that when the scoop-net is placed into a random position among (n - r + 1)·(m - r + 1) possible positions, the average number of caught fishes is as high as possible.

格里沙正与圣诞老人一起庆祝新年时，米沙送给萨沙一个尺寸为 $n \times m$ 的小型矩形池塘，池塘被划分为若干个 $1 \times 1$ 的方格，每个方格中至多有一条微小的邪恶鱼（否则它们会互相争斗！）。

礼物套装中还附带一个尺寸为 $r \times r$ 的方形渔网。若该渔网的左下角位于方格 $(x, y)$ 处，则位于正方形区域 $(x, y),\dots,(x + r - 1, y + r - 1)$ 内的所有鱼都会被捕获。注意：使用渔网时，其必须完全置于池塘内部。

不幸的是，萨沙的钓鱼技术并不娴熟，因此他总是随机抛掷渔网。为了不让萨沙感到沮丧，米沙决定向空池塘中放入 $k$ 条鱼，使得捕获鱼的期望数量尽可能大。请帮助米沙！换言之，请将 $k$ 条鱼放入池塘中互不相同的方格内，使得当渔网在全部 $(n - r + 1) \cdot (m - r + 1)$ 种可能位置中等概率随机放置时，捕获鱼的平均数量达到最大。

The only line contains four integers n, m, r, k (1 ≤ n, m ≤ 105, 1 ≤ r ≤ min(n, m), 1 ≤ k ≤ min(n·m, 105)).

唯一一行包含四个整数 $n$、$m$、$r$、$k$（$1 \leq n, m \leq 10^5$，$1 \leq r \leq \min(n, m)$，$1 \leq k \leq \min(n \cdot m, 10^5)$）。

Print a single number — the maximum possible expected number of caught fishes.

You answer is considered correct, is its absolute or relative error does not exceed 10 - 9. Namely, let your answer be a, and the jury's answer be b. Your answer is considered correct, if .

输出一个整数——即最多可能捕获的鱼的期望数量。

若你的答案的绝对误差或相对误差不超过 $10^{-9}$，则视为正确。也就是说，设你的答案为 $a$，评测组的答案为 $b$，当满足

时，你的答案即为正确。

In the first example you can put the fishes in cells (2, 1), (2, 2), (2, 3). In this case, for any of four possible positions of the scoop-net (highlighted with light green), the number of fishes inside is equal to two, and so is the expected value.

在第一个例子中，你可以将鱼放在单元格 (2, 1)、(2, 2)、(2, 3) 中。此时，对于渔网勺可能的四个位置（图中以浅绿色高亮显示），每个位置内鱼的数量均为 2，因此期望值也为 2。