27ος ΠΔΠ Καμπ (κοινά)
Μετοχές και K χτυπήματα (metoxes)

Μια χρηματιστηριακή εταιρεία θέλει να αξιολογήσει μια πρακτική αγοράς και πώλησης μετοχών που είναι γνωστή ως στρατηγική των \(K\) χτυπημάτων.

Γνωρίζουμε τις τιμές \(p_1, p_2, \ldots, p_N\) μίας μετοχής για χρονικό διάστημα \(N\) ημερών. Η εταιρεία προτίθεται να αγοράσει και να πουλήσει τη μετοχή αυτή το πολύ \(M\) φορές μέσα σε αυτό το χρονικό διάστημα. Έστω λοιπόν ότι θα γίνουν \(K \leq M\) αγοραπωλησίες και έστω ότι κατά την \(i\)-οστή από αυτές η εταιρεία θα αγοράσει τη μετοχή τη μέρα \(b_i\) και θα την πουλήσει τη μέρα \(s_i\). Τα χρονικά διαστήματα \([b_i, s_i]\) δεν επικαλύπτονται, δηλαδή: \(1 \leq b_1 < s_1 < b_2 < s_2 < \ldots < b_K < s_K \leq N\). Το συνολικό κέρδος \(X\) της εταιρείας από όλες τις αγοραπωλησίες είναι προφανώς:

\[X = \sum_{i = 1}^K (p_{s_i} - b_{s_i})\]

Η εταιρεία θέλει να βρεί πόσα χτυπήματα πρέπει να κάνει και πότε, ώστε να μεγιστοποιήσει το κέρδος \(X\). Δηλαδή, θέλει να προσδιορίσει την τιμή του \(K\) και τα όρια των διαστημάτων \([b_i, s_i]\).

Αρχεία Εισόδου (metoxes.in):

Η πρώτη γραμμή της εισόδου θα περιέχει δύο φυσικούς αριθμούς \(N\) και \(M\): το πλήθος των ημερών και το μέγιστο πλήθος χτυπημάτων. Η δεύτερη γραμμή της εισόδου θα περιέχει \(N\) ακέραιους αριθμούς \(p_i\), χωρισμένους μεταξύ τους με ένα κενό διάστημα: τις τιμές της μετοχής.

Αρχεία Εξόδου (metoxes.out):

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς ένα φυσικό αριθμό: το μέγιστο κέρδος \(X\) που μπορεί να επιτευχθεί με το πολύ \(M\) χτυπήματα.

Παραδείγματα Αρχείων Εισόδου - Εξόδου:

1^o

metoxes.in	metoxes.out
10 3 12 12 7 10 15 8 3 4 8 8	13

Εξήγηση 1^ου παραδείγματος: Στο πρώτο παράδειγμα, η εταιρεία μπορεί να πετύχει το μέγιστο κέρδος κάνοντας μόνο \(2\) χτυπήματα:

• αγοράζει την 3η μέρα στην τιμή \(7\) και πουλάει την 5η μέρα στην τιμή \(15\)
• αγοράζει την 7η μέρα στην τιμή \(3\) και πουλάει την 9η μέρα (ή τη 10η) στην τιμή \(8\) Έτσι το κέρδος της είναι \((15−7)+(8−3)=13\). Αυτό είναι το μέγιστο δυνατό.

2^o

metoxes.in	metoxes.out
5 2 10 9 8 7 6	0

Εξήγηση 2^ου παραδείγματος: Στο δεύτερο παράδειγμα, η τιμή της μετοχής πέφτει κάθε μέρα, οπότε το μέγιστο δυνατό κέρδος είναι μηδέν, αν δε γίνει κανένα χτύπημα.

Περιορισμοί

• \(1 \leq N \leq 100.000\).
• \(0 \leq M \leq 1.000\).
• \(1 \leq p_i \leq 10.000\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.
• Όριο μνήμης: \(64\) MB.