2400: Dusa And The Yobis

Memory Limit:128 MB Time Limit:1.000 S
Creator:
Submit:60 Solved:34

Description

Dusa eats Yobis, but only Yobis of a certain size. If Dusa encounters a Yobi that is smaller than itself, it eats the Yobi, and absorbs its size. For example, if Dusa is of size 10 and it encounters a Yobi of size 6, Dusa eats the Yobi and expands to size 10 + 6 = 16. If Dusa encounters a Yobi that is the same size as itself or larger, Dusa runs away without eating the Yobi. Dusa is currently facing a line of Yobis and will encounter them in order. Dusa is guaranteed to eventually encounter a Yobi that causes it to run away. Your job is to determine Dusa’s size when this happens.
Dusa吃Yobis,但只吃特定大小的Yobis。 如果Dusa遇到比它小的Yobis,它就会吃掉Yobis,并吸收其大小。 例如,如果Dusa的大小为10,它遇到一个大小为6的Yobis,Dusa就会吃掉Yobis,扩大到大小10 + 6 = 16。 如果Dusa遇到一个与自己大小相同或更大的Yobis,Dusa就会逃跑,不会吃掉Yobis。 Dusa目前面对着一排Yobis,并将按顺序遇到它们。保证Dusa最终会遇到一个使它逃跑的Yobis。你的任务是确定这发生时Dusa的大小。

Input

The first line of input contains a positive integer, D, representing Dusa’s starting size. 
The remaining lines of input contain positive integers representing the sizes of the Yobis in order.
第一行输入包含一个正整数D,代表Dusa的起始大小。 
接下来的行输入包含正整数,代表按顺序的Yobis的大小。

Output

Output the positive integer, R, which is Dusa’s size when it eventually runs away. 
输出正整数R,即Dusa最终逃跑时的大小。

Sample Input

5
3
2
9
20
22
14

Sample Output

19

HINT

Dusa is large enough to eat the Yobi of size 3. This brings Dusa’s size to 8. Dusa is large enough to eat the Yobi of size 2. This brings Dusa’s size to 10. Dusa is large enough to eat the Yobi of size 9. This brings Dusa’s size to 19. The Yobi of size 20 causes Dusa to run away. 
Dusa足够大,可以吃掉大小为3的Yobi。这使Dusa的大小增加到8。Dusa也足够大,可以吃掉大小为2的Yobi。这使Dusa的大小增加到10。Dusa还能吃掉大小为9的Yobi。这使Dusa的大小增加到19。然后,大小为20的Yobi使Dusa逃跑。

Source/Category