兑换礼品

题目描述

小零和小壹面对一个电子装置，正面有 n 个排成一列的按钮，按钮编号为 1 到 n，标签颜色共有 k 种，颜色用 0..k-1 表示。每个按钮对应一个可用积分兑换礼品的礼盒。当只有一人按下按钮时，装置没有反应；只有两人同时按动两个标签颜色相同的按钮时，这两个按钮之间的所有按钮（包括这两个按钮）所对应的礼盒都会被激活。

两人一共有 p 分，求有多少种选择两个按钮的方案，使得被激活的礼盒中至少有一个礼盒的兑换积分不超过 p 分。

输入格式

输入数据有 n+1 行。

第一行三个整数 n, k, p，每两个整数之间用一个空格隔开，分别表示按钮的个数、标签颜色的数目和两人的积分值。

接下来的 n 行，每行两个整数，第 i+1 行表示第 i 号按钮的标签颜色 Ai 和该按钮对应礼盒的兑换积分要求 Bi。

输出格式

输出一行一个整数，表示可选择按钮的方案总数。

样例

输入：

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

输出：

3

数据范围

• 2 <= n <= 200000
• 1 <= k <= 50
• 0 <= p <= 100
• 0 <= Ai < k
• 0 <= Bi <= 100

选择两个按钮时必须满足它们的标签颜色相同，并且这两个按钮之间（包括端点）至少存在一个礼盒的兑换积分 Bi <= p。