Why Did the Cow Cross the Road III

题目描述

农夫约翰年事已高，不幸变得越来越暴躁且多疑。他忘记了多年来牛群多样性对农场繁荣的帮助，最近决定在农场周围建起一道巨大的围栏，阻止邻近农场的奶牛来访，并且完全禁止少数几个邻近农场进入。奶牛们对这种状况十分不满，不仅因为她们再也无法拜访朋友，还因为这导致她们取消参加国际挤奶奥林匹亚大赛——这是她们一年到头都期待的活动。

仍然能够进入农夫约翰农场的邻居奶牛发现进入过程变得更加艰难，因为她们只能通过一个大门进入，并且每头牛都要接受严格盘问，常常导致奶牛们排起长队。

对于来访的 $N$ 头奶牛中的每一头，你会得到她到达大门的时间，以及她回答入场问题所需的持续时间。任意时刻只能有一头牛正在接受盘问，因此如果许多奶牛在相近时间到达，她们很可能需要排队依次处理。例如，如果一头牛在时间 5 到达并回答问题用时 7 个时间单位，那么另一头在时间 8 到达的牛需要等到时间 12 才能开始回答问题。

请确定所有奶牛都能进入农场的最早可能时间。

输入格式

第一行输入 $N$，一个不超过 100 的正整数。 接下来的 $N$ 行每行描述一头奶牛，给出她到达的时间以及接受盘问所需的时间；这两个数都是不超过 1,000,000 的正整数。

输出格式

请输出所有奶牛都完成处理的最小可能时间。

3
2 1
8 3
5 7

15

提示

这里，第一头牛在时间 2 到达并很快处理完成。大门随后短暂空闲，直到第三头牛在时间 5 到达并开始处理。第二头牛在时间 8 到达，等待到时间 5+7=12 才能开始回答问题，并在时间 12+3 = 15 完成。 题目贡献者：Brian Dean

标签: USACO|2017|Bronze

来源

USACO|2017|Bronze