国际象棋停车安全问题

Time Limit: 1000 ms Memory Limit: 65536 KiB

Problem Description

相信大家都听说过国际象棋的八皇后问题,现在我们来看一下国际象棋中另外一个棋子——车,它可以向东南西北四个方向驰骋,也是威力强大的一个棋子。但现在我们要讨论的“车”略有不同,它只能在东西或南北方向上行动。我们要在一个N*M的矩形棋盘上安置若干辆“车”,每个格子只能放一辆“车”,在停放这些“车”时,我们可以指定每一辆“车”的停放方向,它们可以选择东西方向,使它只能威胁到它东西方向上的格子;或者选择南北方向,威胁到它南北方向上的格子。有R个格子是已经预留了车位,我们一定要把“车”放在上面:除了放在预留格的“车”外,还有C个“车”必须放进棋盘。请选择一种放置方案,使没受到“车”威胁到格子总数最多,并输出没受威胁的格子总数。

Input

第一行由4个整数组成。分别是N(1<=N<=100),M(1<=M<=100),R(1<=R<=20),C(1<=C<=20)。下面是R个预留格子的坐标,每个坐标由两个整数X,Y(1<=X<=N,1<=Y<=M)组成,占一行。

Output

输出没受威胁的格子总数即可。

Sample Input

3 3 2 3
1 2
2 1

Sample Output

4

Hint

上述答案可用图1表示:(横杆表示东西方向的车,竖杆表示南北方向的车)

Source