You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

信号灯

题目描述

校园开放日开始了，小 J 需要沿着一条固定路线前往主会场。

路线中共有 $n$ 个信号灯。小 J 从时刻 $0$ 出发。通过第 $i-1$ 个信号灯后，他需要行走 $x_i$ 秒到达第 $i$ 个信号灯。特别地，到达第一个信号灯前也需要先行走 $x_1$ 秒。

第 $i$ 个信号灯按照如下规则不断循环变化：

• 绿灯持续 $g_i$ 秒；
• 随后红灯持续 $r_i$ 秒；
• 然后重新进入绿灯，重复以上过程。

所有信号灯都从时刻 $0$ 开始计时。也就是说，在每个长度为 $g_i+r_i$ 的周期内：

• 当 $0 \le t \bmod (g_i+r_i) < g_i$ 时，第 $i$ 个信号灯为绿灯；
• 否则，第 $i$ 个信号灯为红灯。

当小 J 到达一个信号灯时：

• 若当前为绿灯，他可以立刻通过；
• 若当前为红灯，他必须等待到下一次绿灯开始后才能通过。

通过信号灯本身不消耗时间。

请你求出小 J 通过最后一个信号灯时的时刻。

输入格式

第一行一个整数 $n$，表示信号灯的数量。

接下来 $n$ 行，每行三个整数 $x_i,g_i,r_i$，分别表示到达第 $i$ 个信号灯前需要行走的时间、绿灯持续时间和红灯持续时间。

输出格式

输出一个整数，表示小 J 通过最后一个信号灯时的时刻。

样例输入

3
4 5 3
3 4 4
2 3 5

样例输出

10

样例解释

• 小 J 于时刻 $4$ 到达第一个信号灯。此时 $4 \bmod 8=4<5$，为绿灯，可以直接通过。
• 他于时刻 $7$ 到达第二个信号灯。此时 $7 \bmod 8=7\ge 4$，为红灯，因此等待至时刻 $8$。
• 他于时刻 $10$ 到达第三个信号灯。此时 $10 \bmod 8=2<3$，为绿灯，可以直接通过。

因此答案为 $10$。

数据范围

对于所有测试数据：

• $1 \le n \le 10^5$；
• $1 \le x_i,g_i,r_i \le 10^9$。

提示

答案可能超过 int 的表示范围，请使用 long long 存储时间。