241983 - 检验流水线

题目描述

社区医院的检验科每天要处理一批血液样本。一份样本送来之后,必须先放进离心机分离血清,离心完成后立刻转到分析仪上做检测。检验科只有一台离心机和一台分析仪,每台仪器同一时刻只能处理一份样本。

今天一共送来了 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。

标签
题目参数
时间限制 1 秒
内存限制 128 MB
提交次数 6
通过人数 2
金币数量 2 枚
难度 基础


上一题 下一题