Description

2020年4月，数学家约翰·康威（John H. Conway）因新冠肺炎去世。大家回顾康威教授平生贡献时，不可避免要提到伟大、深刻的“康威生命游戏”（Conway's Game of Life）。康威生命游戏规则极简，就是在方格子（细胞）根据周围八个方格情况判断是存活、或者死亡。用简单规则就可以演变出震撼人心的宏大场景。

规则如下：（周围包括该细胞上、下、左、右、左上、左下、右上与右下）

1.“人口过少”：如果一个活细胞周围的活细胞个数少于2个，则该细胞死亡。

2.“正常”：如果一个活细胞周围有2个或3个细胞为生，则保持存活。

3.“人口过多”：如果一个活细胞周围有大于等于4个细胞为生，则该细胞死亡。

4.“繁殖”：如果一个死细胞周围有3个细胞为生，则该细胞为生。

而下面这几张图，全是依照上方四条简单规则运行的产物。（点击名字查看GIF动画）

“脉冲星“：它的周期为3，看起来像一颗周期爆发的星星。

“滑翔者“：每4个回合“它”会向右下角走一格。虽然细胞早就是不同的细胞了，但它能保持原本的形态。

“轻量级飞船”：它的周期是4，每2个回合会向右边走一格。

“滑翔者枪”：它会不停地释放出一个又一个滑翔者。

“繁殖者”：它会向右行进，留下一个接一个的“滑翔者枪”。动图最后一帧定格时用三种颜色区分了繁殖者本体、滑翔者枪和它们打出来的滑翔者。

给出地图的行数$R$和列数$C$，以及$N$个存活细胞的坐标(其它位置为死细胞)，求经过$T$回合后的存活细胞总数。

Input Format

第一行依次给出$R$，$C$，$N$，$T$。($1\leq R \leq50$，$1\leq C \leq50$，$0\leq N \leq2500$，$0\leq T \leq2000$)

接下来N行，每一行给出一个存活细胞的坐标$y_{i}$，$x_{i}$。($1\leq y_{i} \leq R$，$1\leq x_{i} \leq C$)

Output Format

在一行中输出按给出T个回合后地图中存活细胞的个数。

10 10 5 7
1 2
2 3
3 1
3 2
3 3

5

13 20 7 13
8 10
9 10
10 10
8 11
8 12
9 12
10 12

42