← 返回题目列表

Codeforces · 1195/E

E. 开放街道地图

中文机器翻译题面 查看原题

Seryozha 开设了一门专门构建 Stepanovo 娱乐中心高度地图的课程。他在地图上放置了一个大小为 $$$n \times m$$$ 个单元格的矩形网格(网格的行从北到南编号为 $$$1$$$ 到 $$$n$$$,列从西到东编号为 $$$1$$$ 到 $$$m$$$)。之后,他测量了雷宾斯克海平面以上每个单元的平均高度,并获得了大小为 $$$n \times m$$$ 的高度矩阵。单元格 $$$(i, j)$$$ 位于第 $$$i$$$ 行和第 $$$j$$$ 列的交集处,高度为 $$$h_{i, j}$$$。

Seryozha 将在浏览器中查看他的工作结果。 Seryozha 笔记本电脑的屏幕可以容纳大小为 $$$a \times b$$$ 的子矩形,其高度矩阵 ($$$1 \le a \le n$$$, $$$1 \le b \le m$$$)。 Seryozha 试图确定天气如何影响娱乐中心——例如,如果下雨,所有的雨水都会聚集在那里。为此,他将在笔记本电脑屏幕上显示的所有单元格中找到高度最小的单元格。

帮助 Seryozha 计算他在屏幕上看到的所有可能的子矩形的此类单元格的高度总和。换句话说,您必须计算所有 $$$1 \le i \le n - a + 1$$$ 和 $$$1 \le j \le m - b + 1$$$ 中大小为 $$$a \times b$$$ 且左上角为 $$$(i, j)$$$ 的子矩阵的最小高度之和。

考虑序列 $$$g_i = (g_{i - 1} \cdot x + y) \bmod z$$$。给定整数 $$$g_0$$$、$$$x$$$、$$$y$$$ 和 $$$z$$$。巧合的是, $$$h_{i, j} = g_{(i - 1) \cdot m + j - 1}$$$ ($$$(i - 1) \cdot m + j - 1$$$ 是索引)。

输入

输入的第一行包含四个整数 $$$n$$$、$$$m$$$、$$$a$$$ 和 $$$b$$$ ($$$1 \le n, m \le 3\,000$$$, $$$1 \le a \le n$$$, $$$1 \le b \le m$$$) — 矩阵 Seryozha 中的行数和列数有,以及笔记本电脑屏幕上可以分别显示的行数和列数。

输入的第二行包含四个整数 $$$g_0$$$、$$$x$$$、$$$y$$$ 和 $$$z$$$ ($$$0 \le g_0, x, y < z \le 10^9$$$)。

输出

打印一个整数——问题的答案。

示例

输入 #1

3 4 2 1
1 2 3 59

输出 #1

111

注意

第一个示例的矩阵: