← 返回比赛

已结束 GESP欢乐赛#50

← 上一题下一题 →

A5049 | $农场修缮$

时间限制1s

内存限制128MB

通过 / 提交0/0

题目描述

在上一段故事里，小明开垦了荒地之后，他现在拥有了一大片农场！ 小明的农场可以看做是一个 $n \times m$ 的网格。为了方便在农场中穿行，小明决定在农场中修建一条水平的道路和一条竖直的道路（显然二者会有一定的面积重合）。 现在他决定修建一条宽度为 $a$ 的水平通路，对于竖直的通路，他会在 $q$ 个备选宽度中选择一个宽度，建造竖直通路。 请问最终小明的农田除去道路以外，能够用于种粮食的面积最大还有多少？ （可以证明剩余面积只和两条道路的宽度有关， 和具体位置无关）

输入格式

输入第一行给定四个整数 $n, m, a, q ( 1 \le a \le n \leq 10000, 1 \le m \le 10000)$。 第二行给出 $q$ 个整数, $b_1, b_2 \cdots b_q (1 \le b_i \le m)$, 代表可以选择的宽度。

输出格式

输出一个整数， 代表能够用于种粮食的最大剩余面积是多少.

输入输出样例

输入 #1

4 4 2 2
2 3

输出 #1

C++ 编辑器

输入

输出