Farmer John 年老後越來越暴躁多疑。忘了牛群多樣性多年如何助農場興旺,決定圍巨大柵欄,阻止鄰場牛來訪,並全禁少數鄰場牛進入。牛很沮喪,不僅不能訪友,還須取消全年期待的國際擠奶奧林匹克賽。
仍可進入的鄰牛也更困難:只過一門,每牛嚴格盤問,常排長隊。
給 $N$ 來訪牛到門時間與回答入場問題時間。同時僅問一牛,近同時到須逐一排隊。例一牛5到問7,另一8到須等12才答。
求全部可進入的最早時間。
輸入格式
首行 $N$,正整數至多100。後 $N$ 行牛到達及問答時間,均正整數至多1,000,000。
輸出格式
求全部完成處理的最早時間。
範例
輸入格式 1
3 2 1 8 3 5 7
輸出格式 1
15
說明
首牛2到很快處理,門空閒至第三牛5到盤問。第二8到等 $5+7=12$ 開始,$12+3 = 15$ 完成。
題目作者:Brian Dean