Unique Umbrella Determination

We are given an \(n\times m\) grid and a hidden umbrella occupying a contiguous subrectangle of size \(x\times y\) (the umbrella cannot be rotated). Each day, rain falls on the grid: between \(1\) and \(k\) cells are chosen (without repetition) and are marked with a drop of rain; however, any cell already having a drop will not receive another drop, and any cell under the umbrella remains dry. At the end of each day, you are given the status of every cell (rain or no rain) but not the locations where the rain fell that day. In other words, you see the pattern of wet/dry cells but not the actual rain events.

The umbrella is completely transparent so you cannot identify it directly from the grid status. Instead, you are allowed to delete (i.e. mark as having rain) at most \(k\) cells per day from anywhere in the grid except the umbrella cells. In the best‐case scenario, you can choose the cells to delete (avoiding the real umbrella) in order to eventually uniquely determine the location of the umbrella.

Formally, assume that the hidden umbrella occupies some \(x\times y\) subrectangle (unknown to you) in the \(n\times m\) grid. Every day you are allowed to choose at most \(k\) cells (which must lie outside the true umbrella) and mark them as having rain (if they are not already wet). Your task is to determine the minimum number of days and the minimum total number of cell deletions required so that there is exactly one \(x\times y\) subrectangle that is completely free of deletions. It is guaranteed that a solution exists.

Hint: One way to think about the problem is as a set covering problem. Each potential \(x\times y\) subrectangle (possible umbrella location) must contain at least one deleted cell except for the true one. In the best case, by a clever choice we can achieve a minimum total number of deletions of

[ D = n + m - x - y, ]

and then the minimum number of days is

[ \text{days} = \left\lceil\frac{n + m - x - y}{k}\right\rceil. ]

inputFormat

The input consists of a single line containing five space‐separated integers: \(n\), \(m\), \(x\), \(y\) and \(k\).

• \(n\) and \(m\) (\(1 \le n, m \le 10^9\)) represent the grid dimensions.
• \(x\) and \(y\) (\(1 \le x \le n,\; 1 \le y \le m\)) represent the dimensions of the umbrella.
• \(k\) (\(1 \le k \le 10^9\)) is the maximum number of cells that can be deleted per day.

outputFormat

Output two space‐separated integers: the minimum number of days needed and the minimum total number of cell deletions required.

Recall that if \(D = n + m - x - y\) is the minimum number of deletions, then the minimum days is \(\lceil D/k \rceil\).

sample

3 3 2 2 1

2 2