题目描述

有一个 $n\times n$ 的正方形点阵，有 $m$ 个玩家同时在棋盘上大战小 Y。第 $i$ 个玩家在棋盘上有自己的领地格点 $(x_i,y_i)$，表示第 $x_i$ 行、第 $y_i$ 列。

为了确保胜利，小 Y 需要使其他 $m$ 个玩家的领地所在的格点都被轰炸。为此，他有两种轰炸方式：

1. 选择一个格点进行轰炸，需要花费 $c$ 枚金币；
2. 选择以正方形上任意一条边上的一段为底边作等腰直角三角形，允许退化成点，并对在该等腰直角三角形内，包括边界上的格点进行轰炸，需要花费覆盖格点个数的金币。

第二种操作要求等腰直角三角形的三个顶点都是格点，并且三角形完全在正方形内，包括边界。

小 Y 想知道使所有给定格点都被轰炸所需的最小金币数。

输入格式

第一行包含三个正整数 $n,m,c$，分别表示棋盘大小、玩家个数以及轰炸单个格点需要花费的金币数量。

接下来 $m$ 行，每行包含两个正整数 $x_i,y_i$，表示第 $i$ 个玩家的领地在 $(x_i,y_i)$。

输出格式

输出一个数，表示小 Y 需要花费的最小金币数量。

样例 1 输入

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

样例 1 输出

7

数据范围

对于所有数据，保证：

$$1\le n,m\le 5\times 10^4, \qquad 1\le c\le 5, \qquad 1\le x_i,y_i\le n.$$

测试点	$n$	$m$	$c$	$x_i,y_i$
1,2,3,4	$\le 4$	$\le 5\times 10^4$	$\le 5$	$1\le x_i,y_i\le n$
5,6	$\le 10$	$20$
7,8,9,10	$\le 1000$	$\le 5\times 10^4$
11	$\le 5\times 10^4$		$=1$
12		$\le n$	$\le 5$	$x_i=y_i=i$
13		$\le 5\times 10^4$		$x_i=1$
14,15,16		$\le 5$		$1\le x_i,y_i\le n$
17,18		$\le 5\times 10^4$		保证 $(x_i,y_i)$ 不在主、副对角线上
19,20				$1\le x_i,y_i\le n$