社区医院的检验科每天要处理一批血液样本。一份样本送来之后,必须先放进离心机分离血清,离心完成后立刻转到分析仪上做检测。检验科只有一台离心机和一台分析仪,每台仪器同一时刻只能处理一份样本。
今天一共送来了 n 份样本。第 i 份样本在时刻 a_i 送到检验科(样本按送达时刻从小到大给出,可能有两份样本同时送到),它需要离心 p_i 分钟,离心完成后需要分析 q_i 分钟。一份样本一旦开始离心,就要连续进行 p_i 分钟不能中断,分析同样不能中断。
如果一份样本送到时离心机正忙,它就在离心机前排队等待;离心机空出来时,排在队首的样本立刻上机。离心完成的样本立刻排到分析仪的队尾,分析仪空出来时队首的样本立刻上机。
请计算最后一份样本分析完成时的时刻。时刻从 0 开始计数。
第一行,一个整数 n,表示样本数量。
接下来 n 行,每行三个整数 a_i、p_i、q_i,依次表示第 i 份样本的送达时刻、离心时长和分析时长。
输出一个整数,表示最后一份样本分析完成时的时刻。
3 0 3 2 2 2 4 9 1 1
11
1 7 2 3
12
2 0 5 1 1 1 5
11
对于 30% 的数据,1 ≤ n ≤ 100,0 ≤ a_i ≤ 10^4,1 ≤ p_i, q_i ≤ 10^4。
对于 100% 的数据,1 ≤ n ≤ 2 × 10^5,0 ≤ a_i ≤ 10^9,1 ≤ p_i, q_i ≤ 10^9,答案不超过 4 × 10^14。