题目描述

多多制定了一个庞大的旅行计划。具体而言，多多准备去$N$个景点游玩。它还为每个景点设定了优先级，必须先前往优先级高的景点游玩，然后才能前往优先级低的景点，各个景点优先级互不相同。

同时由于各大景点都十分火爆，多多只能在已预约的第$X_i$天前往景点$i$，如果无法按约前往，则只能等过$D_i$天再次前往。即，多多只能在第$X_i$、$X_i+D_i$、$X_i+2D_i$、...天前去景点$i$。

多多一天最多游玩一个景点，请问至少需要几天才能完成它的旅行计划。

输入描述

第一行，一个整数$N$，表示有$N$个景点。

接下来$N$行, 每行有三个整数$P_i$, $X_i$, $D_i$

• $P_i$ 是景点$i$优先级，数字越小，表示优先级越高
• $X_i$ 是针对景点$i$的初次预约时间
• $D_i$ 是允许再次前往的天数间隔

$1 \leq N, P_i \leq 100000$. $1 \leq X_i, D_i \leq 1000$.

输出描述

一个整数，表示完成旅行计划的天数

样例

输入

2
1 2 2
2 1 3

输出

4

说明

1号景点优先级最高。

第2天前往1号景点，然后只能在第4天前往2号景点，因此共4天。

样例

输入

3
3 2 3
1 3 2
2 2 2

输出

5