P9548 "PHOI-1" Rain Falling

**The formal statement has been revised.** Tonight, the rain keeps falling... 

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.

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

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.

**This problem uses bundled tests.** | Subtask | $n,m$ | $x,y$ | Score | | :-: | :-: | :-: | :-: | | $0$ | $1\le n,m\le 10$ | No special constraints | $10$ | | $1$ | $1\le n,m\le 10^3$ | No special constraints | $30$ | | $2$ | No special constraints | $x=y=2$ | $10$ | | $3$ | No special constraints | $1 \le x=y \le 10^9$ | $10$ | | $4$ | No special constraints | No special constraints | $40$ | 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