Background

The formal statement has been revised.

Tonight, the rain keeps falling...

Problem Description

On an empty field with $n$ rows and $m$ columns, there is an umbrella of size $x$ rows and $y$ columns. The umbrella cannot be rotated. Every day, $1 \sim k$ raindrops are randomly sprinkled onto the field. A cell that already has rain will not receive rain again, and a cell covered by the umbrella will not get wet.

This umbrella is special: it is completely transparent, so Xiao X cannot directly know its position. However, after each day ends, Xiao X will learn the state of every cell on the field, i.e. whether it has a raindrop or not. Note that Xiao X only learns the final state of the cells. Xiao X cannot know where it rained each day.

Now Xiao X wants you to compute, in the best case (i.e. with the minimum number of days), how many days are needed to make the umbrella position unique, and after the umbrella position is known, the minimum possible number of raindrops on the field. The testdata guarantees that a solution exists.

Formally, there is an $n \times m$ rectangle. Each day you can delete at most $k$ cells. Ask for the minimum number of days and the minimum number of deleted cells needed to make the complete $x \times y$ rectangle in the figure unique.

Input Format

One line with $5$ integers: $n,m,x,y,k$.

Output Format

One line: the number of days needed to know the umbrella position in the best case, and after the umbrella position is known, the minimum number of raindrops on the field. Output the two values separated by a space.

4 4 2 2 3

1 3

7 5 3 2 2

3 5

214 748 3 64 8

98 782

Hint

This problem uses bundled tests.

For $100\%$ of the data, it is guaranteed that $1 \le x \le n \le 10^9,1 \le y \le m \le 10^9,1 \le k \le 10^9$.

Sample Explanation #1:

On the first day, let raindrops fall at $(2,2),(2,3),(3,2)$, and you can determine that the top-left and bottom-right corners of the umbrella are $(3,3),(4,4)$.

Illustration:

Sample Explanation #2:

On the first day, let raindrops fall at $(2,2),(7,1)$. On the second day, let a raindrop fall at $(5,4)$. On the third day, let raindrops fall at $(4,2),(3,4)$. Then you can determine that the top-left and bottom-right corners of the umbrella are $(5,2),(7,3)$.

Constraints

Translated by ChatGPT 5