← 返回题目列表

AtCoder · tessoku_book_fn

C16. 航班

中文机器翻译题面 查看原题

配点: 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