行文午后谨防昼寝巨龙， 误受其害难免伏案不醒， 思绪漫步远避哈欠连天， 午后暖阳不啻催眠妖精。

给定 $m$ 个 $[1,n)$ 数轴上的区间 $[l_i,r_i)$。你需要计算有多少个区间 $[L,R]$ 满足 $1\le L\le R\le m$，且存在至少 $k$ 个 $p\in [1,n]$，满足存在集合 $S \subseteq \{L,L+1,\dots ,R\}$ 使得以下条件成立：

• $\forall x,y\in S,x\ne y$，区间 $[l_x,r_x)$ 和区间 $[l_y,r_y)$ 不交。
• $\bigcup_{j\in S} [l_j,r_j)=[1,p)$。

输入格式

第一行三个整数 $n,m,k$。

下面 $m$ 行，第 $i+1$ 行两个整数 $l_i,r_i$。

输出格式

一个整数表示答案。

样例 1

input

4 3 3
1 2
2 3
3 4

output

2

样例 2

input

5 5 4
1 3
3 5
1 2
2 4
4 5

output

5

数据范围

本题采用捆绑测试。

对于所有数据，保证 $2\le n\le 10^5$，$1\le m\le 10^5$，$1\le k\le n$，$1\le l_i < r_i\le n$。

时间限制：$4\texttt{s}$

空间限制：$512\texttt{MB}$