Shopping Plans

Αγοράζετε από ένα κατάστημα που πουλά ένα σύνολο ~N~ αντικειμένων. Το ~i~-οστο αντικείμενο έχει ένα τύπο ~a_i~ το οποίο είναι ένας ακέραιος μεταξύ του ~1~ και του ~M~. Ένα εφικτό σχέδιο αγορών είναι ένα υποσύνολο από αυτά τα αντικείμενα τέτοιο ώστε για όλους τους τύπους ~j~, ο αριθμός των αντικειμένων τύπου ~j~ να ανήκει στο διάστημα [~x_j~, ~y_j~].

Το ~i~-οστο αντικείμενο στο κατάστημα έχει κόστος ~c_i~ και το κόστος ενός σχεδίου αγορών είναι το άθροισμα από τα κόστη των αντικειμένων του σχεδίου. Σας ενδιαφέρει το πιθανό κόστος των εφικτών σχεδίων αγορών. Βρείτε το κόστος από τα ~K~ πιο φθηνά εφικτά σχέδια αγορών. Σημειώστε ότι αν υπάρχουν δύο διαφορετικά σχέδια αγορών με το ίδιο κόστος, θα πρέπει να μετρηθούν ξεχωριστά στην έξοδο.

Είσοδος

Η πρώτη γραμμή αποτελείται από τρεις, χωρισμένους με κενό, ακέραιους ~N~, ~M~ και ~K~ (~1~ ~\le~ ~N~, ~M~, ~K~ ~\le~ ~200\,000~). Ακολουθούν ~N~ γραμμές, η ~i~-οστη από τις οποίες περιέχει δύο, χωρισμένους με κενό, ακέραιους ~a_i~ και ~c_i~ (~1~ ~\le~ ~a_i~ ~\le~ ~M~, ~1~ ~\le~ ~c_i~ ~\le~ ~10^9~). Ακολουθούν ~M~ γραμμές, η ~j~-οστη από τις οποίες περιέχει δύο, χωρισμένους με κενό, ακέραιους ~x_j~ και ~y_j~ (~0~ ~\le~ ~x_j~ ~\le~ ~y_j~ ~\le~ ~N~).

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~x_j~ = ~y_j~ = ~1~ και ~N~, ~M~, ~K~ ~\le~ ~4\,000~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~x_j~ = ~y_j~ = ~1~ και ~N~, ~M~, ~c_i~ ~\le~ ~4\,000~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~x_j~ = ~y_j~ = ~1~.

Για επιπλέον ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~x_j~ = ~0~.

Έξοδος

Εκτυπώστε ~K~ γραμμές. Στην ~i~-οστη γραμμή, εκτυπώστε το κόστος του ~i~-οστου φθηνότερου σχεδίου αγορών, αν υπάρχει, ή -1 αν υπάρχουν λιγότερα από ~i~ εφικτά σχέδια αγορών.

Παράδειγμα

input

5 2 7
1 5
1 3
2 3
1 6
2 1
1 1
1 1

output

4
6
6
7
8
9
-1

Επεξήγηση του παραδείγματος

Ένα εφικτό σχέδιο αγορών πρέπει να συνδιάζει ακριβώς ένα αντικείμενο με κόστος στο {~5~, ~3~, ~6~} με ακριβώς ένα αντικείμενο με κόστος στο {~3~, ~1~}.