题目描述
展带上一排 $n$ 个展位,每个展位有装饰色($0 \sim k-1$)和一个咖啡角(有最低消费)。
两位参观者想选两个不同展位落脚,要求:
- 两展位装饰色相同;
- 两人展位之间(含两端)存在至少一个最低消费不超过 $p$ 的咖啡角。
求可行的落脚方案总数。
输入格式
第一行三个整数 $n, k, p$;
接下来 $n$ 行,每行两个整数:展位的装饰色与咖啡角最低消费。
输出格式
一行一个整数:可行方案总数。
数据范围
$$1 \le n \le 2 \times 10^5$$
,$$1 \le k \le 50$$
,$$0 \le p, \text{消费} \le 10^4$$
。
样例输入 #1
5 2 3
0 5
1 3
0 2
1 4
1 5
样例输出 #1
3
样例输入 #2
100 5 10
2 3226
0 8803
0 5480
4 4784
2 5561
3 1011
4 9028
1 2523
0 4663
1 7973
4 3998
1 3000
1 8668
1 2329
3 246
1 8602
2 9983
1 4536
4 3817
2 6725
2 9015
1 7821
2 3032
4 6595
4 7289
2 3084
4 2229
4 5446
4 4213
4 8838
4 2831
0 1320
3 9874
2 422
0 2221
0 8406
2 6816
3 4499
2 6131
3 2800
0 8353
1 1956
4 1135
2 206
2 9050
2 8326
4 3020
2 7137
4 9724
4 8167
1 5030
4 8221
2 7633
4 1715
1 976
1 1679
4 3905
3 8778
0 2323
0 10000
3 7985
1 3161
0 7123
0 7368
4 1455
4 9910
4 3166
0 5074
1 9407
0 420
4 5286
0 6337
0 3762
0 3840
2 5582
1 4168
1 1386
2 9937
2 7699
2 7059
0 186
1 7832
1 8585
3 3696
3 6222
2 3163
3 4987
4 9970
0 4706
3 5680
0 4692
1 7249
1 6209
4 6276
3 6669
1 5503
1 9944
1 5064
2 7973
1 7940
样例输出 #2
0