CST-ის ოლიმპიადა

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

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

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

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


CST-ის ფაკულტეტზე ჩატარდა ოლიმპიადა, რომლის მიზანია შეარჩიოს გუნდი მსოფლიო პირველობისათვის ინფორმატიკაში. სტუდენტების რაოდენობა ფაკულტეტზე არის N (1 <= N <= 100). ოლიმპიადამ თითოეული სტუდენტი შეაფასა ორი კრიტერიუმით: - ალგორითმების ცოდნა Si (-1000 <= Si <= 1000)  და  კოდის წერის უნარი Fi (-1000 <= Fi <= 1000) კოეფიციენტებით.

ახლა საჭიროა შეირჩეს სტუდენტთა ნაკრები მსოფლიო ოლიმპიადისათვის. ფაკულტეტის ხელმძღვანელობა თვლის, რომ ალგორითმებში ნაკრების ჯამური ცოდნა TS არის ნაკრებში შემავალი სტუდენტების Si-ების ჯამი. ასევე, ნაკრების კოდის წერის უნარი TF არის სტუდენტების კოდის წერის უნარების Fi-ების ჯამი. ფაკულტეტის ხელმძღვანელობას უნდა, რომ მის მიერ შერჩეულ ნაკრებს ჰქონდეს TS-ის და TF-ის მაქსიმალურად დიდი ჯამი. მაგრამ, ამავე დროს, მას უნდა, რომ ეს ორივე კოეფიციენტი ცალ-ცალკე აუცილებლად არაუარყოფითი იყოს. დაეხმარეთ მათ არჩევანის გაკეთებაში.

 

შეტანის ფორმატი:

სტრიქონი 1: ერთი მთელი რიცხვი N, სტუდენტების რაოდენობა

სტრიქონები 2..N+1: ორი, ჰარით გამოყოფილი მთელი რიცხვი Si და Fi, თითოეული სტუდენტის ალგორითმების ცოდნის და კოდის წერის უნარის მაჩვენებელი.

 

გამოტანის ფორმატი:

სტრიქონი 1: ერთი მთელი რიცხვი: TS და TF კოეფიციენტების მაქსიმალური ჯამი, იმის გათვალისწინებით, რომ თითოეული მათგანი არაუარყოფითია. იმ შემთხვევაში, თუ არ არსებობს სტუდენტების ისეთი ნაკრები, რომლის TS და TF არაუარყოფითია, გამოიტანეთ 0.




მაგალითები

შესატანი მონაცემები
5 -5 7 8 -6 6 -3 2 1 -8 -5 დაკოპირება
გამოსატანი მონაცემები
8 დაკოპირება

შენიშვნა

უნდა ავირჩიოთ სტუდენტები 1, 3, და 4, მათი კოეფიციენტებია TS = -5+6+2 = 3 და TF = 7-3+1 = 5, აქედან 3+5 = 8. შევნიშნავთ, რომ თუ ნაკრებში ჩავრთავდით მე-2 სტუდენტსაც, მაშინ კოეფიციენტების ჯამი იქნებოდა TS+TF= 10, მაგრამ, ასეთ შემთხვევაში, კოეფიციენტი TF უარყოფითი იქნებოდა.