{"problem":{"name":"「PHOI-1」雨纷纷","description":{"content":"在 $n$ 行 $m$ 列的空地上，有一个大小为 $x$ 行 $y$ 列的伞，雨伞不可以旋转。每天向空地随机洒下 $1 \\sim k$ 滴雨，已经有雨的格子不会再降下雨，有伞的格子不会被雨淋湿。 但此伞比较特殊，它完全透明，小 X 无法直接得知伞的位置。但是每天结束后，小 X 都会得知空地上每个空格的状态，即有雨滴或无雨滴。注意，小 X 只会得知格子的状态。小 X 无法得知每天在哪里降了雨。 ","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P2"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP9548"},"statements":[{"statement_type":"Markdown","content":"在 $n$ 行 $m$ 列的空地上，有一个大小为 $x$ 行 $y$ 列的伞，雨伞不可以旋转。每天向空地随机洒下 $1 \\sim k$ 滴雨，已经有雨的格子不会再降下雨，有伞的格子不会被雨淋湿。\n\n但此伞比较特殊，它完全透明，小 X 无法直接得知伞的位置。但是每天结束后，小 X 都会得知空地上每个空格的状态，即有雨滴或无雨滴。注意，小 X 只会得知格子的状态。小 X 无法得知每天在哪里降了雨。\n\n现在小 X 想让你求出**在最好情况下**（即天数最少时）几天可以使伞的位置唯一，以及得到伞的位置后，场上至少的雨滴数量，数据保证有解。\n\n**形式化的讲**，有一个 $n \\times m$ 的矩形，你每天可以**至多**删除 $k$ 个格子。问至少需要多少天以及至少需要删除多少格子，才能使得图中完整的 $x\\times y$ 的矩形唯一。\n\n## Input\n\n一行，$5$ 个整数，分别为 $n,m,x,y,k$。\n\n## Output\n\n一行，分别为**在最好情况下**几天可以得知伞的位置，以及得到伞的位置后，场上至少的雨滴数量，两个数据用空格隔开。\n\n[samples]\n\n## Background\n\n**形式化题面的表述已更改。**\n\n今夜，雨纷纷……\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/aec4ykim.png)\n\n## Note\n\n**本题采用捆绑测试。**\n\n| Subtask | $n,m$ | $x,y$ |  分值 |\n| :-: | :-: | :-: | :-: |\n| $0$ | $1\\le n,m\\le 10$ | 无特殊限制 | $10$ |\n| $1$ | $1\\le n,m\\le 10^3$ | 无特殊限制 | $30$ |\n| $2$ | 无特殊限制 | $x=y=2$ | $10$ |\n| $3$ | 无特殊限制 | $1 \\le x=y \\le 10^9$ | $10$ | \n| $4$ | 无特殊限制 | 无特殊限制 | $40$ | \n\n对于 $100\\%$ 的数据，保证 $1 \\le x \\le n \\le 10^9,1 \\le y \\le m \\le 10^9,1 \\le k \\le 10^9$。\n\n### 样例解释 #1：\n\n第一天在 $(2,2),(2,3),(3,2)$ 处落下雨滴，即可确定雨伞左上角以及右下角位置为 $(3,3),(4,4)$。\n\n图片解释：\n\n![](https://cdn.luogu.com.cn/upload/image_hosting/fp2m6ivv.png)\n### 样例解释 #2：\n\n第一天在 $(2,2),(7,1)$ 处落下雨滴，第二天在 $(5,4)$ 处落下雨滴，第三天在 $(4,2),(3,4)$ 处落下雨滴，即可确定雨伞左上角以及右下角位置为 $(5,2),(7,3)$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP9548","tags":["模拟","贪心","O2优化"],"sample_group":[["4 4 2 2 3","1 3"],["7 5 3 2 2","3 5"],["214 748 3 64 8","98 782"]],"created_at":"2026-03-03 11:09:25"}}