Pretty Pens

Παρακολουθείτε ένα μάθημα καλλιτεχνικών και η τρέχουσα εργασία σας είναι αρκετά αλγοριθμική.

Έχετε ~N~ στυλό, καθένα από τα οποία έχει ένα μόνο χρώμα, που αναπαρίσταται από έναν ακέραιο αριθμό από το ~1~ έως το ~M~. Αρχικά, το χρώμα του ~i~-οστού στυλό δίνεται από το ~C_i~. Επιπλέον, τα στυλό σας είναι όμορφα, με το ~i~-οστό στυλό να έχει βαθμό ομορφιάς ~P_i~.

Για την εργασία σας, πρέπει να δημιουργήσετε μια εικόνα χρησιμοποιώντας ~M~ πινελιές, καθεμία από διαφορετικό χρώμα στυλό. Η ομορφιά της εικόνας σας είναι το άθροισμα των βαθμών ομορφιάς των στυλό που χρησιμοποιήθηκαν για τη δημιουργία της εικόνας.

Ο δάσκαλός σας σάς έχει δώσει κάποιο περιθώριο καλλιτεχνικής ελευθερίας: πριν δημιουργήσετε αυτή την όμορφη εικόνα, επιτρέπεται να αλλάξετε το χρώμα το πολύ ενός στυλό σε οποιοδήποτε άλλο χρώμα. Αφού σχεδιαστεί η εικόνα, το στυλό θα επανέλθει στο αρχικό του χρώμα.

Ο δάσκαλός σας θα σας δώσει ~\frac{1}{3}~ των βαθμών (~5~ από τους ~15~ συνολικά) για την εργασία των καλλιτεχνικών, με βάση το πόσο όμορφη εικόνα μπορείτε να δημιουργήσετε.

Για να ωθήσει ακόμη περισσότερο την καλλιτεχνία σας, ο δάσκαλος σάς δίνει επίσης ~Q~ επιπλέον εικόνες για να δημιουργήσετε, οι οποίες αποτελούν τα υπόλοιπα ~\frac{2}{3}~ των βαθμών (~10~ από τους ~15~ συνολικά) της εργασίας σας. Πριν από κάθε εικόνα, θα πραγματοποιείται μία από δύο πιθανές αλλαγές στο σύνολο των διαθέσιμων στυλό:

• 1 i c υποδεικνύει ότι το χρώμα του ~i~-οστού στυλό αλλάζει σε ~c~.
• 2 i p υποδεικνύει ότι ο βαθμός ομορφιάς του ~i~-οστού στυλό αλλάζει σε ~p~.

Οι αλλαγές εκτελούνται διαδοχικά (έτσι, η πρώτη αλλαγή τροποποιεί την αρχική κατάσταση, η δεύτερη αλλαγή τροποποιεί το αποτέλεσμα της εφαρμογής της πρώτης και ούτω καθεξής).

Όπως και στην πρώτη εικόνα που δημιουργήσατε, επιτρέπεται να αλλάξετε το χρώμα το πολύ ενός στυλό πριν δημιουργηθεί η εικόνα. Σημειώστε ότι, αν αλλάξετε το χρώμα ενός στυλό, αυτό επηρεάζει μόνο την επόμενη εικόνα που θα σχεδιάσετε και το στυλό θα επανέλθει στο προηγούμενο χρώμα του πριν εφαρμοστεί η επόμενη αλλαγή, εάν υπάρχει.

Ποια είναι η ομορφιά των πιο όμορφων ~Q + 1~ εικόνων που μπορείτε να δημιουργήσετε;

Είσοδος

Η πρώτη γραμμή της εισόδου θα περιέχει τρεις ακέραιους αριθμούς ~N~, ~M~ και ~Q~ χωρισμένους με κενά (~1 \le M \le N \le 200.000,\ 0 \le Q \le 200.000)~.

Οι επόμενες ~N~ γραμμές θα περιέχουν από δύο ακέραιους αριθμούς ~C_i~ και ~P_i~ χωρισμένους με κενό, όπου ~1 \le C_i \le M~ και ~1 \le P_i \le 10^9~, οι οποίοι υποδεικνύουν το χρώμα και τον βαθμό ομορφιάς του ~i~-οστού στυλό.

Οι επόμενες ~Q~ γραμμές θα περιέχουν τρεις ακέραιους αριθμούς. Ο πρώτος είναι είτε ~1~ είτε ~2~.

Αν ο πρώτος ακέραιος είναι ~1~, ακολουθείται από δύο ακέραιους ~i_j~ και ~c_j~, όπου ~1 \le i_j \le N~ και ~1 \le c_j \le M~, που αναπαριστούν μια αλλαγή του χρώματος του ~i_j~-οστού στυλό σε ~c_j~.

Αν ο πρώτος ακέραιος είναι ~2~, ακολουθείται από δύο ακέραιους ~i_j~ και ~p_j~, όπου ~1 \le i_j \le N~ και ~1 \le p_j \le 10^9~, που αναπαριστούν μια αλλαγή του βαθμού ομορφιάς του ~i_j~-οστού στυλό σε ~p_j~.

Είναι εγγυημένο ότι αρχικά και μετά από κάθε αλλαγή, υπάρχει τουλάχιστον ένα στυλό με καθένα από τα ~M~ χρώματα.

Ο ακόλουθος πίνακας δείχνει πώς κατανέμονται οι ~15~ διαθέσιμοι βαθμοί:

Βαθμοί	Όρια των ~N~ και ~M~	Όρια του ~Q~	Επιπλέον Περιορισμοί
~5~	~1 \le M \le N \le 200.000~	~Q = 0~	Κανένας επιπλέον περιορισμός.
~2~	~M = 1,\; 1 \le N \le 200.000~	~0 \le Q \le 200.000~	Κανένας επιπλέον περιορισμός.
~2~	~M = 2,\; 2 \le N \le 200.000~	~0 \le Q \le 200.000~	Κανένας επιπλέον περιορισμός.
~2~	~M \le 10,\; 1 \le M \le N \le 200.000~	~0 \le Q \le 200.000~	Κανένας επιπλέον περιορισμός.
~2~	~1 \le M \le N \le 200.000~	~0 \le Q \le 200.000~	Όλες οι τιμές ομορφιάς είναι διαφορετικές.
~2~	~1 \le M \le N \le 200.000~	~0 \le Q \le 200.000~	Κανένας επιπλέον περιορισμός.

Έξοδος

Η έξοδος θα αποτελείται από ~Q + 1~ γραμμές, όπου η ~j~-οστή γραμμή περιέχει έναν ακέραιο, τη μέγιστη δυνατή τιμή ομορφιάς που μπορεί να επιτευχθεί αφού έχουν πραγματοποιηθεί οι πρώτες ~j - 1~ αλλαγές.

input

6 3 0
1 6
2 9
3 4
2 7
3 9
1 3

output

25

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

Υπάρχουν έξι διαθέσιμα στυλό σε τρία διαφορετικά χρώματα. Το σύνολο των στυλό είναι:

• δύο στυλό χρώματος ~1~, με βαθμούς ομορφιάς ~6~ και ~3~,
• δύο στυλό χρώματος ~2~, με βαθμούς ομορφιάς ~9~ και ~7~,
• δύο στυλό χρώματος ~3~, με βαθμούς ομορφιάς ~4~ και ~9~.

Αν δεν αλλάξουμε το χρώμα κανενός στυλό, η πιο όμορφη εικόνα έχει ομορφιά ~6 + 9 + 9 = 24~.

Ωστόσο, αν αλλάξουμε το χρώμα του στυλό ~4~ από χρώμα ~2~ σε χρώμα ~1~, μπορούμε να δημιουργήσουμε μια εικόνα με ομορφιά ~7 + 9 + 9 = 25~, η οποία είναι η πιο όμορφη εικόνα που μπορεί να δημιουργηθεί.

input

3 2 2
1 20
2 30
1 10
1 3 2
2 3 25

output

50
50
55

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

Υπάρχουν τρία στυλό με δύο διαφορετικά χρώματα διαθέσιμα.

Πριν από την πρώτη αλλαγή, η χρήση του στυλό ~1~ και του στυλό ~2~, με χρώματα ~1~ και ~2~ αντίστοιχα, επιτυγχάνει ομορφιά ~20 + 30 = 50~.

Μετά την πρώτη αλλαγή, το στυλό ~3~ έχει χρώμα ~2~. Δεν υπάρχει αλλαγή στη μέγιστη ομορφιά, ακόμη και αν μπορούσαμε να αλλάξουμε το χρώμα ενός στυλό: η επιλογή των στυλό ~1~ και ~2~ δίνει τη μέγιστη ομορφιά.

Μετά τη δεύτερη αλλαγή, το στυλό ~3~ έχει χρώμα ~2~ και βαθμό ομορφιάς ~25~. Πριν δημιουργηθεί η τελική εικόνα, μπορούμε να αλλάξουμε το χρώμα του στυλό ~2~ σε χρώμα ~1~ και να χρησιμοποιήσουμε τα στυλό ~2~ και ~3~, επιτυγχάνοντας τη μέγιστη ομορφιά ~30 + 25 = 55~.