Abigail 是一名正在学习成为铁匠的学徒。她想要规划自己的学习轨迹，以便在成为著名专家的过程中尽可能多地打造宝剑。

共有 $n$ 位师傅愿意收她为徒。第 $i$ 位师傅从第 $a_i$ 分钟开始工作，到第 $b_i$ 分钟结束，总共工作 $b_i - a_i$ 分钟。在这段时间内，Abigail 可以在这位师傅的锻造炉工作。她可以多次进出锻造炉，每次到达时可以打造一把或多把宝剑。然而，为了在第 $i$ 位师傅的指导下打造一把宝剑，她必须连续工作 $t_i$ 分钟。她不能将宝剑打造到一半就离开，并在下次到达该锻造炉时继续完成。

请帮助 Abigail 制定一个最优计划，并计算她在 $n$ 位师傅的指导下最多能打造多少把宝剑。

输入格式

第一行包含一个整数 $n$ ($1 \le n \le 200\,000$)，表示师傅的人数。

接下来的 $n$ 行，每行包含三个整数 $a_i, b_i, t_i$ ($1 \le a_i < a_i + t_i \le b_i \le 10^{18}$)，分别表示师傅工作的开始时间、结束时间，以及在该锻造炉打造一把宝剑所需的时间。

输出格式

输出 Abigail 使用最优学习轨迹所能打造的宝剑的最大数量。

样例

样例 1

输入

2
5 7 1
1 9 2

输出

5

说明

样例 2

输入

3
1 10 4
6 12 3
9 13 2

输出

4

说明

样例 3

输入

3
1 13 4
6 11 2
9 13 3

输出

4

说明