Рибки#8793
Поки Гриша зустрічає Новий Рік у компанії Діда Мороза, Міша дарує Саші невеликий прямокутний ставок розміром n \times m, поділений на клітинки розміром 1 \times 1. У кожній клітинці може бути не більше однієї злої рибки.
Разом зі ставком Саша отримує сачок розміром r \times r для ловлі риби. Якщо лівий нижній кут сачка помістити у клітинку з координатами , то будуть спіймані всі рибки у квадраті від до (x + r - 1, y + r - 1). Зауважте, що сачок має повністю знаходитися всередині ставка при використанні.
Саша новачок у рибальстві та кидає сачок випадковим чином. Щоб вона не засмучувалася через погані результати, Міша вирішив стратегічно розмістити рибок у різних клітинках порожнього ставка так, щоб математичне сподівання кількості спійманих риб було максимальним. Допоможіть Міші розмістити рибок так, щоб при випадковому киданні сачка в одну із (n - r + 1) \times (m - r + 1) можливих позицій середня кількість риб у сачку була максимальною.
В одному рядку задано цілі числа: , , , (1 \le n, m \le 10^5, 1 \le r \le \min(n, m), 1 \le k \le \min(n \cdot m, 10^5)).
Виведіть одне число — максимальне можливе математичне сподівання кількості спійманих риб.
Ваша відповідь буде зарахована, якщо її абсолютна або відносна похибка не перевищує 10^{-5}.
Приклад 1
Приклад 2