题目描述

小 X 的学校制定了一套徽章体系。学校老师经常会结合同学们的表现，给相应同学发放徽章，以此表扬进步，鼓励同学再接再厉。徽章有各式类型，例如“皮卡丘徽章”“小火龙徽章”“杰尼龟徽章”“喵喵徽章”……深受同学们的喜爱。

这些徽章一共有 M 种类型，可以编号 1～M。很多同学都把集齐 M 种徽章作为自己最大的年度梦想。但集齐徽章是相当不容易的，因为同一天内，每名同学至多只会得到一枚徽章，也有可能得不到徽章；而在不同的两天，同一名同学所得到的徽章又有可能是重复的。

小 X 也特别希望得到这些徽章。但对于任何一天，他只关心这一天能否得到徽章，以及能否在过去至多连续 D 天内（包括这一天）集到 K 种不同的徽章——如果两者都可以，小 X 就会觉得这一天是一个“开心的日子”。

现在，如果告诉你小 X 分别在哪几天得到了具体哪种类型的徽章，你能计算出开学至今，小 X 总共有多少个“开心的日子”吗？

输入格式

输入共 N+1 行，第一行包括五个用空格隔开的整数 T、N、M、D 和 K。前三个整数依次表示开学至今共 T 天，其中有 N 天小 X 获得了徽章，学校徽章共 M 种。某一天如果能被认为是一个“开心的日子”，则这一天小 X 应获得一枚徽章，并且在过去至多连续 D 天内（包括这一天）小 X 应集到 K 种不同的徽章。

接下来 N 行，每行包括两个用空格隔开的整数 tᵢ 和 kᵢ，表示在开学的第 tᵢ 天，小 X 获得了一枚编号 kᵢ 的徽章。注意：保证这 N 行按 tᵢ 升序排列。

输出格式

输出只有一行，包括一个整数，表示开学第 1～T 天内小 X 共有多少个“开心的日子”。

输入样例 #1

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

输出样例 #1

2

输入样例 #2

1 1 1 1 1
1 1

输出样例 #2

1

输入样例 #3

10 3 2 2 2
1 1
5 2
10 1

输出样例 #3

0

数据范围与约定

对于 50% 的数据，1≤D,T≤1,000。

对于 80% 的数据，1≤D,T≤10^6。

对于 100% 的数据，1≤D,T≤10^9，1≤N,M≤2×10^5，K≤M，tᵢ,D,N≤T 且 tᵢ<tᵢ₊₁。