eolymp
bolt
Спробуйте наш новий інтерфейс для відправки розв'язків
Задачі

Рибки

Рибки

Ліміт часу 1 секунда
Ліміт використання пам'яті 64 MiB

Поки Гриша зустрічає Новий Рік в компанії Діда Мороза, Міша дарить Саші невеликий прямокутний ставок розміром n·m, розділений на клітинки розміром 1·1, в яких знаходяться злі рибки, не більше однієї на клітинку.

Разом зі ставком, в комплекті іде сачок розміром r·r, яким можна ловити рибу. Так, якщо помістити лівий нижній край сачка в клітинку з координатами (x,y), то будуть спіймані всі рибки в квадраті (x,y)...(x+r-1,y+r-1). Відмітимо, що в процесі сачок повинен повністю знаходитися всередині ставка.

На жаль, Саша зовсім недосвідчена в благородному мистецтві ловлі риби, тому закидає сачок випадковим чином. Щоб вона не засмучувалась через погані результати, Міша вирішив випустити в різні клітинки пустого ставка k рибок так, що математичне очікування кількості зловлених риб було максимальне. Допоможіть йому цього досягнути і порадувати Сашу! А саме, розмістітьk риб так, що при закиданні сачка в випадкове з (n-r+1)·(m-r+1) положень середня кількість риб в сачку була максимально можлива.

Вхідні дані

В єдиному рядку знаходиться 4 числа n, m, r, k (1 ≤ n, m ≤ 10^5, 1 ≤ r ≤ min(n,m), 1 ≤ k ≤ min(n·m, 10^5)).

Вихідні дані

Виведіть єдине число – максимально можливе математичне очікування кількості пійманих риб.

Відповідь буде зарахована, якщо її відносна або абсолютна похибка не перевищує 10^(-5)

Приклад

Вхідні дані #1
3 3 2 3
Вихідні дані #1
2.0000000000
Вхідні дані #2
12 17 9 40
Вихідні дані #2
32.8333333333