You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

采摘水果

描述

在一个风景优美的果园里，有一排长长的果树，一共有 $n$ 棵果树，这些果树按照其种植顺序从 $1$ 到 $n$ 编号。每一棵果树只结一种水果（共有 $k$ 种水果，用整数 $0 \sim k-1$ 表示），而且每棵果树的水果都标有一个采摘难度值。

两位果农决定到果园里采摘水果。他们希望采摘相同种类的水果，但为了不争抢，他们会选择两棵不同的果树采摘。采摘结束后，他们计划在两棵果树之间（包括这两棵果树）找到一棵果树，休息并享受采摘的成果。然而，他们对休息的果树也有要求：果树的采摘难度值不能超过 $p$。

现在，他们想知道有多少种选择采摘果树的方案，能够保证他们找到一棵满足条件的果树休息。

输入格式

输入包含 $n+1$ 行。

• 第一行三个整数 $n, k, p$，每两个整数之间用一个空格隔开，分别表示果树的数量，水果种类的数量以及可接受的采摘难度的最大值；
• 接下来的 $n$ 行，每行两个整数，分别表示第 $i$ 棵果树的水果种类 $a_i$ 和采摘难度值 $b_i$。

输出格式

一个整数，表示满足条件的果树选择方案的总数。

输入样例 1

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

输出样例 1

3

样例解释

两位果农要采摘相同种类的水果，所有可选的采摘方案包括：采摘果树①③，②④，②⑤，④⑤。

然而，若选择果树 $4$ 和 $5$，果树 $4$ 和 $5$ 之间的采摘难度最大值是 $4$，超过了他们能接受的难度值 $3$，因此这种方案不满足要求。

最终只有前 $3$ 种方案可选。

数据范围

• 对于 $30\%$ 的数据，有 $n \leq 100$；
• 对于 $50\%$ 的数据，有 $n \leq 1\,000$；
• 对于 $100\%$ 的数据，有 $2 \leq n \leq 2 \times 10^5$，$1 \leq k \leq 50$，$0 \leq p \leq 100$，$0 \leq b_i \leq 100$。