問題文

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)

入力例 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