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