本题子任务设置相比原题做了细微调整。增加了子任务 5 和 6，满分调整为 110。

时间限制： 2.0 秒

空间限制： 512 MB

题目描述

Charlie 喜欢在钉子板上用橡皮筋绑出各种图形。今天，他玩的钉子板上已经有了 $n$ 根钉子，他想绑出一个面积尽可能大的图形，且图形内部没有钉子（但边和顶点上可以有）。但 Charlie 不会计算复杂形状的面积，所以他最后决定只绑矩形，且要求矩形的边和钉子板的外围平行。他很快发现为了达到只绑矩形的目的，他不得不在钉子板上插入新的钉子辅助，但 Charlie 不想插入太多新钉子，每插入一根新钉子都有一定的代价。请你帮 Charlie 找到一个绑矩形的方式，他的收益是矩形面积减去插入新钉子的总代价，他的目标是收益尽量大。

钉子板是一个矩形，默认左下角顶点坐标为 $(0,0)$，右上角顶点坐标是 $(l,r)$，其中 $l,r$ 均为整数。钉子的坐标均为整数，钉子可以出现在钉子板的边缘。Charlie 插入的新钉子必须在整数坐标，可以插 在钉子板的边缘。每根新钉子的代价为 $w$。

输入格式

从标准输入读入数据。

输入第一行包含四个正整数 $l,r,w,n$，其中含义如题目所描述。

接下来 $n$ 行，每行包含两个整数 $x_i,y_i$，满足 $0\le x_i\le l,~0\le y_i\le r$，表示每个钉子的坐标。数据保证所有钉子的坐标互不相同。

输出格式

输出到标准输出。

输出一个整数，为 Charlie 的最大收益，该收益可以为负值。

5 5 3 6
0 0
0 2
1 4
2 3
3 2
4 1

3

样例 1 解释

在 $(3,0)$ 处新增一个钉子，然后以 $(0,0),(3,0),(3,2),(0,2)$ 为顶点圈出一个面积为 $6$ 的矩形，总收益为 $6-3=3$。

5 5 10 1
2 2

-21

样例 2 解释

在 $(5,2),(5,5),(2,5)$ 处各新增一个钉子，然后以 $(2,2),(5,2),(5,5),(2,5)$ 为顶点圈出一个面积为 $9$ 的矩形，总收益为 $9-3\times 10=-21$。

子任务

对于所有数据，保证 $1\le n\le 5000,~0\le l,r,w\le 10^9$。

本题采用捆绑测试，你只有通过一个子任务中的所有测试点才能得到该子任务的分数。