Fish#8793
Grisha is celebrating New Year with Santa Claus, and meanwhile, Misha gifts Sasha a small rectangular pond of size n \times m, divided into cells of size 1 \times 1. Each cell can contain at most one angry fish.
Along with the pond, Sasha receives a net of size r \times r for catching fish. If the bottom-left corner of the net is placed at cell coordinates , it will catch all fish within the square defined by to (x + r - 1, y + r - 1). Note that the net must be entirely within the pond when used.
Sasha is a beginner at fishing and casts the net randomly. To ensure she is not disappointed by poor results, Misha plans to strategically place fish in different cells of the empty pond to maximize the expected number of fish caught. Help Misha by placing the fish so that, when the net is cast randomly in any of the (n - r + 1) \times (m - r + 1) possible positions, the average number of fish caught is maximized.
A single line contains integers: , , , (1 \le n, m \le 10^5, 1 \le r \le \min(n, m), 1 \le k \le \min(n \cdot m, 10^5)).
Output a single number — the maximum possible expected number of fish caught.
The result will be accepted if its relative or absolute error does not exceed 10^{-5}.
Example 1
Example 2