საკვების შერჩევა

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

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

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

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

წყარო: USACO, 2007/08, DEC, GOLD


N (1 <= N <= 100,000) ძროხა ბალახით კვებას ითხოვს. თითოეული ამბიციურია და ბალახს არ მიეკარება, თუ საკვებს არ გააჩნია საკმარისი ფასი და სიმწვანე.  i-ური ძროხა ითხოვს საკვებად ბალახს მინიმუმ A_i (1 <= A_i <=1,000,000,000) ფასად და B_i (1 <= B_i<= 1,000,000,000) სიმწვანით. ძროხების აჯანყების ასაცილებლად ჯონი საწყობს მიმართავს. საწყობს გააჩნია M (1 <= M <= 100,000) განსხვავებული ბალახი C_i (1 <= C_i <=1,000,000,000) ფასით და D_i (1 <= D_i <= 1,000,000,000) სიმწვანით. გარდა ამისა, საკუთარ ინდივიდუალობაზე ხაზგასამელად, ყველა ძროხას სურს, მისთვის ნაყიდი ბალახი უნიკალური იყოს და სხვა ძროხასაც იგივე ბალახი არ უყიდონ. დაწერეთ პროგრამა, რომელიც ამოარჩევს ბალახის იმ სახეობებს, რითაც შესაძლებელია  ყველა ძროხის გამოკვება მინიმალური ჯამური ხარჯით.

 

შემავალი მონაცემების ფორმატი :

* სტრიქონი 1: ჰარით გამოყოფილი ორი მთელი: N და M

* სტრიქონები 2..N+1: ხაზი i+1 შეიცავენ ჰარით გამოყოფილ ორ მთელს: A_i და B_i

* სტრიქონები N+2..N+M+1: სტრიქონი i+N+1 შეიცავს ჰარით გამოყოფილ ორ მთელს: C_i და D_i

 

 

გამომავალი მონაცემების ფორმატი:

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

 

 

 




მაგალითები

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

შენიშვნა

განმარტება: ძროხა 1 ჭამს 2 ბალახს ფასად 2, ძროხა 2 ჭამს 3 ბალახს ფასად 4, ძროხა 3 ჭამს 6 ბალახს ფასად 2, ძროხა 4 ჭამს 7 ბალახს ფასად 4, რაც ჯამში გვაძლევს 12.