ბანკომატები

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

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

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

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

წყარო: GEOI, 2010, რეგიონული, IX კლასამდე


სახელმწიფო ბანკლადეშში ფუნქციონირებს N(1≤N≤500) ბანკი. თითოეულ მათგანს აქვს ბანკომატების საკუთარი ქსელი, საიდანაც მოსახლეობას ელექტრონული ბარათებით შეუძლია ფულის გამოტანა საკუთარი ანგარიშებიდან. თუმცა ყველა ბანკს არა აქვს ბანკომატი ყველა დასახლებულ პუნქტში, ამიტომ ხშირია შემთხვევა, როცა რომელიმე ბანკის მომხმარებელს სხვა ბანკის ბანკომატიდან გამოაქვს ფული. ბანკებმა მოილაპარაკეს, რომ შექმნან ერთიანი მონაცემთა ბაზა ბანკომატებიდან განხორციელებული ოპერაციებისათვის და ყოველი თვის ბოლოს მოახდინონ ანგარიშსწორება ერთმანეთთან. დაწერეთ პროგრამა, რომელიც გამოითვლის ყველაზე დიდ დავალიანებას ბანკთა ყველა შესაძლო წყვილებს შორის. ცხადია, რომ თუ A1 ბანკის მომხმარებლებმა A2 ბანკის ბანკომატებიდან გაიტანეს X1 თანხა, ხოლო A2 ბანკის მომხმარებლებმა A1 ბანკის ბანკომატებიდან გაიტანეს X2 თანხა და ამასთან X1>X2, მაშინ A2 ბანკს A1-ის მიმართ არა აქვს დავალიანება, ხოლო A1-ს აქვს A2 ბანკის მიმართ დავალიანება X1-X2.

შესატანი მონაცემები: პირველ სტრიქონში მოცემულია ორი ნატურალური რიცხვი N – ბანკების რაოდენობა და M – ერთ თვეში ყველა ბანკომატით შესრულებული ოპერაციების რაოდენობა. მომდევნო M სტრიქონიდან თითოეულში აღწერილია ერთ-ერთი ბანკომატით შესრულებული ოპერაცია და თითოეული სტრიქონი შეიცავს სამ ნატურალურ რიცხვს: ბანკომატის მფლობელი ბანკის ნომერი, იმ ბანკის ნომერი, რომლის მომხმარებელმაც გამოიტანა თანხა ბანკომატიდან და გამოტანილი თანხის რაოდენობა. 

გამოსატანი მონაცემები: გამოიტანეთ ერთი მთელი რიცხვი - ყველაზე დიდი დავალიანება ბანკთა ყველა შესაძლო წყვილებს შორის. გარანტირებულია, რომ პასუხი არ აღემატება 1,000,000-ს.




მაგალითები

შესატანი მონაცემები
4 7 2 1 100 4 4 200 3 1 300 1 3 150 2 2 290 3 1 200 2 4 320 დაკოპირება
გამოსატანი მონაცემები
350 დაკოპირება

შენიშვნა

მეორე და მეხუთე ოპერაციები დავალიანებებზე გავლენას ვერ მოახდენენ, რადგან ბანკის მომხმარებლებმა საკუთარის ბანკის ბანკომატებით ისარგებლეს. პირველი ბანკის მომხმარებლებმა მესამე ბანკის ბანკომატებიდან ჯამურად გამოიტანეს 500 ლარი, ხოლო მესამე ბანკის მომხმარებლებმა პირველი ბანკის ბანკომატიდან – 150 ლარი, ამიტომ პირველი ბანკის დავალიანება მესამესთან შეადგენს 500-150=350 ლარს, რაც მაქსიმალურია მოცემულ სიტუაციაში.