公路收费

题目描述:

XZH 大神犇有一个能力，那就是山的高度！
\(\bf{——\color{red}h\color{black}{uangrenheluogu}}\)

XZH 在一个 \(n\times n\) 的直角坐标系上（如下图所示，但是图没了）。

他需要从 \((0,0)\) 走到 \((n,n)\)。然而，WD 想要趁机敲诈 XZH 一波，XZH 每经过一条边，就要被收一块钱。

但是 XZH 有一个能力，那就是免费。于是，他在坐标系上设置了 \(m\) 个免费点，在经过免费点后，之后走的前 \(t\) 条边都不会被收费。

XZH 想要知道，怎么走收费最少。但是他不会，因此向你求助。

输入格式:

第一行三个整数 \(n,m,t\)。

接下来 \(m\) 行，每行两个整数 \(x,y\) 表示免费点的坐标。

保证 \((x,y)\ne (0,0)\)。

输出格式:

一行一个整数，表示被收的钱数。

样例输入:

样例1
3 2 1
1 1
2 3

样例2
3 3 2
1 0
1 1
2 2

样例输出:

样例1
4

样例2
1

提示:

对于 \(100\%\) 的数据，\(1\le n\le300\)，\(1\le m\le n^2\)，\(1\le t\le n\)。

时间限制: 1000ms
空间限制: 512MB

---

来源: xuzhanghan123