当 Grisha 与 Ded Moroz 庆祝新年时,Misha 送给 Sasha 一个大小为 n × m 的小矩形池塘,分成 1 × 1 大小的单元,里面栖息着微小的邪恶鱼(每个单元不得超过一条鱼,否则它们会发生冲突!)。
礼包还包括一个尺寸为 r × r 的方形勺,专为钓鱼而设计。如果勺网的左下角位于单元格 (x, y),则方格 (x, y)...(x + r - 1, y + r - 1) 内的所有鱼都会被捕获。请注意,使用时舀网应完全位于池塘内。
不幸的是,萨莎钓鱼技术不太好,因此随意抛出勺子。为了不让莎莎沮丧,米莎决定将k条鱼放入空池塘中,以使得捕获的鱼数量的期望值尽可能高。帮助米莎! 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、m、r、k (1 ≤ n, m ≤ 105, 1 ≤ r ≤ min(n, m), 1 ≤ k ≤ min(n·m, 105))。
输出
打印一个数字——预计捕获的鱼的最大可能数量。
你的答案被认为是正确的,其绝对或相对误差不超过10 - 9。即,设你的答案为a,陪审团的答案为b。如果 $$\frac{|a-b|}{\max(1, |b|)} \leq 10^{-9}$$,则您的答案被认为是正确的。
示例
输入 #1
3 3 2 3
输出 #1
2.0000000000
输入 #2
12 17 9 40
输出 #2
32.8333333333
注意
在第一个示例中,您可以将鱼放入单元格 (2, 1)、(2, 2)、(2, 3) 中。在这种情况下,对于勺网的四个可能位置中的任何一个(以浅绿色突出显示),内部鱼的数量等于两条,预期值也等于两条。