Boring Lectures

Έχετε ένα πρόγραμμα με ~N~ προσεχείς διαλέξεις που έχετε την επιλογή να παρακολουθήσετε. Οι διαλέξεις αριθμούνται από το ~1~ έως το ~N~ και είναι με χρονολογική σειρά. Από το τρέχον πρόγραμμα, περιμένετε ότι η ~i~-οστη διάλεξη θα έχει ποιότητα ~a_i~. Δεδομένου ότι οι περισσότερες από τις διαλέξεις θα είναι βαρετές, είστε πρόθυμοι να παρακολουθήσουν μόνο κάποια ομάδα ~K~ διαδοχικών διαλέξεων. Θα παραλείψετε τις υπόλοιπες διαλέξεις έτσι ώστε να μπορείτε να προλάβετε τον ύπνο και να συμμετάσχετε σε διαγωνισμούς προγραμματισμού. Αφού δεν σας αρέσει να παίρνετε σημειώσεις, θα μπορείτε να θυμάστε το περιεχόμενο μόνο από ~2~ από τις διαλέξεις που παρακολουθείτε. Θέλετε να επιλέξετε τις διαλέξεις που παρακολουθείτε και τις ~2~ διαλέξεις που θυμάστε για να μεγιστοποιήσετε το άθροισμα από τις ποιότητες αυτών των ~2~ διαλέξεων.

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

Είσοδος

Η πρώτη γραμμή θα περιέχει τρεις ακέραιους ~N~, ~K~ και ~Q~ (~2 \le N \le 10^6~, ~2 \le K \le N~, ~0 \le Q \le 10^5~). Η δεύτερη γραμμή περιέχει ~N~ ακέραιους ~a_1, ..., a_N~, (~0 \le a_i \le 10^9~). Οι επόμενες ~Q~ γραμμές περιέχουν η καθεμία δύο ακέραιους ~i_j~ και ~x_j~ (~1 \le i_j \le N~, ~0 \le x_j \le 10^9~).

Βαθμολογία

Για ~5~ από τους ~25~ διαθέσιμους βαθμούς, ~Q = 0~. Για επιπλέον ~10~ από τους ~25~ διαθέσιμους βαθμούς, ~N \le 10^4~.

Έξοδος

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

Παράδειγμα

input

4 3 1
6 1 2 4
1 3

output

8
6

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

Για το αρχικό πρόγραμμα, είναι καλύτερο να παρακολουθήσετε τις πρώτες τρεις διαλέξεις και να θυμάστε την πρώτη και την τρίτη, για μια συνολική αξία ~6 + 2 = 8~. Μετά την ανανέωση, είναι καλύτερο να παρακολουθήσετε τις τελευταίες τρεις διαλέξεις και να θυμάστε τις τελευταίες δύο, δίνοντας μια αξία ~2 + 4 = 6~.