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$ 行：

• 第 $1$ 行包含三个整数 $n, k, p$，分别表示魔法塔的数量，魔法属性的种类以及冒险者能接受的最大魔力值；
• 接下来的 $n$ 行，每行两个整数，第 $i+1$ 行表示第 $i$ 座魔法塔的魔法属性和通行费用。

输出格式

输出一个整数，表示满足条件的不同选择方案的总数。

输入样例 1

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

输出样例 1

3

样例说明

冒险者需要选择两座魔法属性相同的塔，所有可选方案包括：选择塔 $1$ 和 $3$，塔 $2$ 和 $4$，塔 $2$ 和 $5$，以及塔 $4$ 和 $5$。

然而，若选择塔 $4$ 和 $5$，这两座塔之间的通行费用最大值为 $4$，超出了冒险者能接受的最大魔力值 $3$，因此不满足条件。

最终，只有前三种方案符合要求，总计 $3$ 种方案。

数据范围与提示

• 对于 $25\%$ 的数据，$n \leq 100$；
• 对于 $40\%$ 的数据，$n \leq 1000$；
• 对于 $80\%$ 的数据，$n \leq 2 \times 10^5$，$1 \leq k \leq 50$；
• 对于 $100\%$ 的数据，$2 \leq n \leq 2 \times 10^6$，$1 \leq k \leq 10^4$，$0 \leq p \leq 100$，$0 \leq$ 通行费用 $\leq 100$。