Sličice

Ο Nikola είναι ένας παθιασμένος συλλέκτης άλμπουμ με εικόνες ποδοσφαιριστών. Αυτός και οι φίλοι του ανταγωνίζονται μεταξύ τους σε ένα παιχνίδι που επινόησαν με βάση τα άλμπουμ των οποίων οι εικόνες συλλέγονται αυτή τη στιγμή. Οι εικόνες σε αυτό το άλμπουμ χωρίζονται σε $n$ ομάδες, καθεμία από τις οποίες έχει ακριβώς $M$ ποδοσφαιριστές. Ο κύριος κανόνας του παιχνιδιού είναι ότι ο συνολικός αριθμός πόντων που κερδίζει ένα άτομο για την ομάδα είναι $B_x$, όπου $x_i$ είναι ο συνολικός αριθμός των μοναδικών φωτογραφιών των ποδοσφαιριστών αυτής της ομάδας, που συλλέγονται από το άτομο. Συμφώνησαν επίσης ότι ο πίνακας $B$ αυξάνεται, δηλαδή το να έχεις περισσότερες μοναδικές εικόνες ποδοσφαιριστών μιας ομάδας σημαίνει ότι έχεις περισσότερους ή ίσους βαθμούς.

Ο Nikola θα ήθελε να κερδίσει όσο το δυνατόν περισσότερους πόντους στο παιχνίδι. Για κάθε ομάδα $x$, είναι γνωστός ο αριθμός των μοναδικών εικόνων που κατέχει αυτή τη στιγμή ο Nikola από αυτήν την ομάδα και είναι $P_x$.

Ο Ivan είναι φίλος του Nikola που έχει ήδη συγκεντρώσει ολόκληρο το άλμπουμ δύο φορές και όταν άκουσε για το παιχνίδι που παίζει ο Nikola με τους φίλους του, αποφάσισε να του δώσει όσες $K$​εικόνες θέλει ο Nikola. Αφού έμαθε για αυτά τα χαρμόσυνα νέα, ο Nikola αναρωτήθηκε ποιος είναι ο μέγιστος αριθμός πόντων που θα μπορούσε να έχει αφού ο Ivan του δώσει $K$ εικόνες. Υπερβολικά ενθουσιασμένος για αυτά τα νέα, δεν μπορεί να μετρήσει και σας παρακαλεί να απαντήσετε στην ερώτησή του.

Είσοδος

Στην πρώτη γραμμή υπάρχουν οι ακέραιοι αριθμοί $N$, $M$ και $K(1\le N,M\le 500,1\le K\le min(N\cdot M,500))$.
Στη δεύτερη γραμμή υπάρχει ένας πίνακας $P$ που αποτελείται από $N$ μη αρνητικούς ακέραιους αριθμούς $(0\le P_i\le M)$.
Στην τρίτη γραμμή υπάρχει ένας πίνακας $B$ που αποτελείται από $M+1$ μη αρνητικούς ακέραιους αριθμούς $(0\le B_i\le 100000)$, ο αριθμός των πόντων που παίρνει ο Nikola για $i$ $(0\le i\le M)$ μοναδικές εικόνες μιας ομάδας.

Για κάθε $t$ μεταξύ 0 και $M-1$ ισχύει $B_t\le B_{t+1}$

Ισχύει επίσης ότι $K\le N\cdot M-(P_1+P_2+...+P_N)$

Έξοδος

Στη μοναδική γραμμή τυπώστε την απάντηση στην ερώτηση του Nikola.

Βαθμολογία

Στα δοκιμαστικές περιπτώσεις συνολικής αξίας 20% των πόντων ισχύει $K=2$

Παραδείγματα

input

4 4 3
4 2 3 1
0 1 3 6 10

output

31

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

Ο Nikola είναι πολύ πιθανό να ζητήσει από τον Ivan να του δώσει μια εικόνα της τρίτης ομάδας και δύο από τη δεύτερη, ώστε η βαθμολογία του να είναι 31 (10 + 10 + 10 + 1).

input

4 3 5
1 1 2 3
0 1 2 3

output

12

input

3 6 2
2 4 1
31 38 48 60 75 91 120

output

206