დროის მენეჯმენტი

დროის ლიმიტი: 1 წმ

მეხსიერების ლიმიტი: 64 მეგაბაიტი

შემავალი მონაცემები: stdin

გამომავალი მონაცემები: stdout

წყარო: USACO, 2008/09, NOV, SILVER


ბიზნესმენმა აღმოაჩინა რომ მან უნდა უკეთ განკარგოს თავისი დრო. მას აქვს შესასრულებელი N საქმე, რომლებიც მიმდევრობითაა გადანომრილი 
1..N (1 <= N <= 1,000). თავისი დროის უკეთ განკარგვისათვის, მან გააკეთა შესასრულებელ საქმეთა სია. საქმე i საჭიროებს შესაბამის
T_i(1 <= T_i <= 1,000) პერიოდს და უნდა დამთავრდეს S_i (1 <= S_i <= 1,000,000) დროისათვის. დღე იწყება მომენტით t=0.
ბიზნესმენს შეუძლია აკეთოს მხოლოდ ერთი საქმე, რომელიც აუცილებლად უნდა
დაამთავროს. ბიზნესმენს უყვარს გვიანობამდე ძილი.
დაეხმარეთ მას, რომ ადგეს რაც შეიძლება გვიან,
მაგრამ თავის დროზე მოასწროს ყველა იმ საქმის გაკეთება, რაც დაგეგმილი აქვს.
 
შესატანი მონაცემები:
სტრიქონი 1: ერთი მთელი რიცხვი N.
სტრიქონები 2..N+1: ხაზი i+1 შეიცავს ორ ჰარით გაყოფილ მთელს: T_i და S_i-ს.
 
გამოტანის ფორმატი:
სტრიქონი 1: უგვიანესი დრო, როცა ბიზნესმენმა უნდა დაიწყოს მუშაობა, ან -1, თუ მას არ შეუძლია სამუშაოების დროზე შესრულება.
 
 
 



მაგალითები

შესატანი მონაცემები
4 3 5 8 14 5 20 1 16 დაკოპირება
გამოსატანი მონაცემები
2 დაკოპირება

შენიშვნა

ბიზნესმენს აქვს 4 საქმე, რომელიც იჭერს 3, 8, 5, და 1 დროის ერთეულს და თითოეული მათგანი უნდა დამთავრდეს 5, 14, 20, და 16 დროის მომენტისათვის.
მან პირველი საქმე უნდა დაიწყოს მომენტისათვის 2. შემდეგ მან უნდა გააკეთოს მეორე, მეოთხე და მესამე საქმე, რათა ყველაფერი მოასწროს დროულად.