Traka

Όπως αναφέρθηκε προηγουμένως, υπάρχουν ~N~ εργάτες στο εργοστάσιο του Mirko. Κατασκευάζουν αυτοκίνητα σε μεταφορική ταινία, με αγωγό. Οι εργάτες συμβολίζονται με τους αριθμούς ~1-~ ο πιο αριστερά, έως ~N-~ ο πιο δεξιά. Καθένας από τους εργάτες κάνει τη συγκεκριμένη δουλειά του και απαιτεί συγκεκριμένο χρόνο για να την ολοκληρώσει.
Η παραγωγή ενός αυτοκινήτου ξεκινά με τον εργάτη #1 (Mirko). Αφού τελείωσε με το μέρος της δουλειάς του, ο εργάτης #2 αναλαμβάνει, μετά ο #3... Όταν ο εργάτης #N τελειώσει με το μέρος του, το αυτοκίνητο τελειώνει. Ο Μίρκο και οι εργάτες του πρέπει να παράγουν ~M~ αυτοκίνητα και πρέπει να τα παράγουν με σειρά από ~1~ έως ~M~.
Για κάθε εργαζόμενο ~i~ γνωρίζουμε τον ~T_i~ - ο χρόνος που απαιτείται για να κάνει το μέρος της δουλειάς του. Για κάθε αυτοκίνητο ~j~ γνωρίζουμε συντελεστή πολυπλοκότητας συναρμολόγησης ~F_j~. Ο χρόνος σε λεπτά για τον εργάτη ~i~ να ολοκληρώσει το μέρος της εργασίας του στο αυτοκίνητο ~j~ υπολογίζεται ως γινόμενο ~T_i \times F_j~.
Αφού κάποιος εργάτης τελειώσει να δουλεύει σε ένα αυτοκίνητο, πρέπει να το δώσει στον επόμενο εργάτη αμέσως, χωρίς καμία καθυστέρηση (περίεργη πολιτική της εταιρείας). Για το λόγο αυτό, ο εργαζόμενος που παραλαμβάνει το αυτοκίνητο πρέπει να είναι ελεύθερος (δεν πρέπει να εργάζεται σε άλλο αυτοκίνητο). Για να εκπληρώσει αυτή την προϋπόθεση, ο Mirko πρέπει να επιλέξει έναν καλό συγχρονισμό για να ξεκινήσει την κατασκευή ενός νέου αυτοκινήτου. Για να είναι αποτελεσματικός, θα περιμένει ελάχιστο αριθμό λεπτών μέχρι να βεβαιωθεί ότι πληρούνται όλες οι προϋποθέσεις που περιγράφονται.

Γράψτε ένα πρόγραμμα το οποίο, λαμβάνοντας υπόψη τους χρόνους εργασίας και τους παράγοντες πολυπλοκότητας για κάθε αυτοκίνητο, θα υπολογίζει τον συνολικό χρόνο που απαιτείται για την παραγωγή όλων των αυτοκινήτων.

Είσοδος

Η πρώτη γραμμή εισόδου περιέχει θετικούς ακέραιους διαχωρισμένους με χώρο ~N\;(1 \leq N \leq 100\,000)~, αριθμό εργαζομένων και ~M\;(1 \leq M \leq 100\,000)~, αριθμό αυτοκινήτων.
Η ~i~-οστή από τις ακόλουθες ~N~ γραμμές περιέχει τον χρόνο εργασίας ~T_i~ για τον εργάτη ~i~.
Η ~j~-οστή από τις ακόλουθες ~M~ γραμμές περιέχει συντελεστή πολυπλοκότητας ~F_j~ για το αυτοκίνητο ~j~.
Ισχύουν αυτές οι συνθήκες: ~1 \leq T_i \leq 10\,000,\;1 \leq F_j \leq 10\,000~.

Έξοδος

Η πρώτη και μοναδική γραμμή εξόδου πρέπει να περιέχει τον απαιτούμενο αριθμό λεπτών.

Βαθμολογία

Σε περιπτώσεις δοκιμής αξίας ~40~% των συνολικών πόντων, το ~N~ και το ~M~ θα είναι το πολύ ~1000~.

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

input

3 3
2
1
1
2
1
1

output

11

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

Μετά από τέσσερα λεπτά, ο πρώτος εργάτης τελειώνει την εργασία στο πρώτο αυτοκίνητο. Μπορεί να αρχίσει να εργάζεται στο δεύτερο αυτοκίνητο αμέσως, αλλά αυτό θα παραβίαζε την προϋπόθεση ότι τα αυτοκίνητα πρέπει να παραδοθούν στους επόμενους εργάτες μόλις τελειώσουν (μετά από επτά λεπτά ο δεύτερος εργάτης θα τελείωνε να εργάζεται στο μέρος του δεύτερου αυτοκινήτου, αλλά τρίτος εργάτης δεν θα ήταν ελεύθερος να αναλάβει, καθώς θα εργαζόταν ακόμα στο πρώτο αυτοκίνητο). Αυτός είναι ο λόγος που η παραγωγή του δεύτερου αυτοκινήτου ξεκινά μετά από πέντε λεπτά. Η παραγωγή του τρίτου αυτοκινήτου ξεκινά μετά από επτά λεπτά. Το πρώτο αυτοκίνητο τερματίζει μετά από οκτώ, το δεύτερο μετά τα εννέα και το τρίτο μετά από έντεκα δευτερόλεπτα. Ο συνολικός χρόνος είναι τότε 11.

input

3 3
2
3
3
2
1
2

output

29

input

4 5
3
2
2
2
3
1
2
1
2

output

55