#P18166. ICPC Inference

ICPC Inference

ICPC Inference

考虑一场有 13 道题的 ICPC 比赛。队伍可以提交程序,结果为正确或错误。

某队第一次正确通过一道题时,通过题数增加 1,总罚时增加该次提交距比赛开始的分钟数,再加上该队此前对这道题的每次错误提交对应的 20 分钟。已经正确通过一道题后,对该题的所有后续提交都被忽略,不影响成绩。

排名首先按通过题数从多到少排序,再按总罚时从少到多排序;仍相同则随机决定先后。

比赛刚结束,共持续 LL 分钟,DD 支队伍提交了 NN 次程序。有正成绩,也就是至少通过一道题的前三名队伍将登上领奖台。

评委暂时不看提交结果,甚至不知道每次提交对应哪一道题。他们只知道提交时间和提交队伍,想知道领奖台可能是什么样子。

请计算可能出现的有序三队序列数。三队分别是第一、第二、第三名,并且都至少通过一道题。忽略最终只有不到三队通过题目的情况。

输入格式

第一行三个整数 N,D,LN,D,L,均满足 3≤N,D,L≤2000003\le N,D,L\le200000。

接下来 NN 行,第 ii 行两个整数 di,tid_i,t_i:

  • 1≤di≤D1\le d_i\le D,表示提交队伍编号;
  • 1≤ti≤L1\le t_i\le L,表示提交时间;
  • 保证 ti≤ti+1t_i\le t_{i+1},提交按时间非降排列,允许同一分钟多次提交。

输出格式

输出一个整数,表示可能的有序前三名队伍序列数。不取模。

样例 1

输入:

4 3 300
1 10
2 25
2 30
3 50

输出:

3

三种可能的领奖台为:

  • (1,2,3):三队各通过一道题,罚时可以是 (10,25,50)、(10,30,50) 或 (10,50,50)。最后一种情况对应 2 号队第一次提交错误、第二次正确且两次都提交同一道题。
  • (1,3,2):三队罚时为 (10,50,50),同分时随机决定 3 号队在 2 号队之前。
  • (2,1,3):2 号队通过两道题,另两队各通过一道题。

样例 2

输入:

4 6 200000
6 1
6 1
1 2
2 2

输出:

4

可能的序列为 (1,2,6)、(2,1,6)、(6,1,2)、(6,2,1)。