配点: 1000 点
問題文
在 KYOPRO 王国 有 N 个机场,每个机场都有 它们的编号最大为 1 减去 N 。
今天 M 航班已安排。i 第 航班在机场 A_i 到时间 访问过 S_i 从机场出发 B_i 到时间 它到达 T_i 。
太郎今天想乘坐尽可能多的飞机。航班之间的转机 1 次 K 分钟。 请打印出您可以乘坐的最大飞机数量。
制約
- 所有输入均为整数
- 2 \leqq N \leqq 100\,000
- 1 \leqq M \leqq 100\,000
- 1 \leqq K \leqq 10^9
- 1 \leqq A_i, B_i \leqq N (1 \leqq i \leqq N)
- 0 \leqq S_i < T_i \leqq 10^9 (1 \leqq i \leqq M)
入力
输入是按以下格式从标准输入给出的。
N M K A_1 S_1 B_1 T_1 \vdots A_M S_M B_M T_M
出力
可登机的最大飞机数量设置为标准输出。 1 请以行的形式输出。
入力例 1
4 5 30 1 100 2 180 2 200 3 300 1 80 3 360 3 400 3 410 3 450 4 600
出力例 1
3