题目描述

Luka 在开卡车，路上有 $n$ 个信号灯。

对于每个信号灯，他都知道红灯和绿灯亮的时间（循环不断重复）。

Luka 开始开车时，所有交通信号灯都呈红色，并且开始循环。

Luka 每秒移动 $1$ 个距离单位。当交通信号灯为红色时，他要停车，直到它变成绿色。

编写一个程序，确定 Luka 需要多少时间才能到达路的尽头。

道路的起点在 $0$ 处，终点在 $l$ 处。

输入格式

第一行两个数 $n, l$，分别表示信号灯的个数和道路的长度。

接下来，$n$ 行中的每行三个整数 $d, r, g$。 $d$ 表示信号灯到道路起点的距离， $r$ 和 $g$ 分别表示红色和绿色信号灯亮的时间。

信号灯将按 $d$ 升序排列。

没有两个交通信号灯将在同一位置。

输出格式

第一行，一个正整数，表示 Luka 到达路的尽头的时间。

2 10
3 5 5
5 2 2 

12

4 30
7 13 5
14 4 4
15 3 10
25 1 1 

36

提示

样例 #1 解释

在第一个示例中，Luka 在第一个信号灯处等待 $2$ 秒。 接着，他将到达第二个交通信号灯，该信号灯为绿色，可以立即通过。

数据规模及规定

对于 $100\%$ 的数据，$1 \le n \le 100$，$1 \le l \le 10^3$，$1 \le d < l$，$1 \le r \le 100$，$1 \le g \le 100$。

说明

• 本题满分 $30$ 分。
• 本题默认开启 O2 优化开关。
• 题目译自 COCI2007-2008 CONTEST #6 T2 SEMAFORI，译者
  https://www.luogu.com.cn/user/219791