题目描述

丽江河边有 $n$ 家客栈，按照位置顺序从 $1$ 到 $n$ 编号。每家客栈都采用 $k$ 种色调中的一种进行装饰，色调用整数 $0\sim k-1$ 表示；每家客栈还设有一家咖啡店，各咖啡店有自己的最低消费。

两位游客想分别入住两家不同但色调相同的客栈。晚上，他们还要选择一家位于两家客栈之间（包括所住客栈）的咖啡店，并且该咖啡店的最低消费不能超过 $p$ 元。

请计算共有多少种满足要求的住宿方案。

输入格式

第一行包含三个整数 $n,k,p$，分别表示客栈数量、色调数量和游客能够接受的最低消费上限。

接下来 $n$ 行，第 $i$ 行包含两个整数 $a_i,b_i$，分别表示第 $i$ 家客栈的色调和该客栈咖啡店的最低消费。

输出格式

输出一个整数，表示满足要求的住宿方案总数。

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

3

5 2 10
0 11
1 5
0 12
0 6
1 11

4

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

3

数据范围

• 对于 $30\%$ 的数据，$n\le 100$；
• 对于 $50\%$ 的数据，$n\le 1000$；
• 对于 $100\%$ 的数据：
  • $2\le n\le 2\times 10^5$；
  • $1\le k\le 50$；
  • $0\le p\le 100$；
  • $0\le b_i\le 100$。