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