有时会有直达目的地的公交车，这很方便。但有时，你需要乘坐两辆或更多的公交车，并在它们之间换乘才能到达最终目的地。令人烦恼的是，从一辆公交车换乘到另一辆时，你往往需要等待下一辆车的到来。如果能安排好行程，让你永远不需要等待换乘，即你乘坐上一辆车到达车站的时间，正好是下一辆换乘公交车到达的时间，那该多好？

输入格式

输入的第一行包含一个整数 $1 \le b \le 1000$，表示你需要乘坐的公交车数量。接下来的 $b$ 行，按你需要乘坐的顺序描述了每条公交线路的时刻表。每行包含三个空格分隔的整数 $0 \le t \le 1,000,000$，$1 \le i \le 1000$，$1 \le d \le 1000$。第一个整数 $t$ 是该线路的第一班车到达你需要上车的站点的时刻。到达时间以 2021 年 1 月 1 日中午之后的分钟数表示。第二个整数 $i$ 指定了该线路公交车的发车间隔。因此，该线路的公交车将在时刻 $t, t + i, t + 2i, t + 3i, \dots$ 到达该站点。第三个整数 $d$ 是你乘坐这辆车到达下车站点的时长（分钟）。在这段时间之后，你下车并换乘下一辆车。

输出格式

输出一行，包含一个整数，表示你应该乘坐第一辆公交车的最早时间（以 2021 年 1 月 1 日中午之后的分钟数表示），使得你可以按顺序换乘所有后续公交车，且在换乘时无需等待。如果不存在这样的时间，输出 -1。

样例

输入 1

3
101 5 100
100000 7 200
0 4 300

输出 1

99956

输入 2

2
0 6 9
0 10 9

输出 2

-1

输入 3

8
122 997 491
808 991 290
172 983 560
928 977 101
570 971 592
357 967 123
429 953 835
199 947 295

输出 3

526173665553865384027818

说明

样例 1：在时刻 99956 乘坐第一辆公交车（该线路从时刻 101 开始，每 5 分钟发一班车）。然后你在时刻 100056 到达第二辆公交车的站点，这正好赶上发车时间。最后你在时刻 100256 从第二辆车换乘到第三辆车。

样例 2：第一辆车的到达时间永远无法与第二辆车的出发时间重合。