23ος ΠΔΠ Γ' Φάση
Fishboats (fishboats)

Σε μία παραλία με σχήμα ευθείας γραμμής υπάρχει μία ψαροταβέρνα, στη συντεταγμένη μηδέν. Δεξιά και αριστερά από την ψαροταβέρνα (σε θετικές και αρνητικές συντεταγμένες) φτάνουν το πρωί κάθε μέρας \(N\) τράτες (ψαρόβαρκες), που κάθε μία έχει φέρει για να πουλήσει \(M\) κιλά ψάρια. Ο ταβερνιάρης, που ξέρει ότι το βράδυ θα έχει πολλή πελατεία, θέλει να αγοράσει όσο γίνεται περισσότερα κιλά ψάρια. Ξεκινάει λοιπόν από την ταβέρνα ακριβώς τη στιγμή που προσδένουν στην παραλία (όλες συγχρόνως) οι τράτες και διανύει απόσταση μίας μονάδας στη μονάδα του χρόνου. Κάθε φορά που φτάνει σε μία τράτα, ο ταβερνιάρης αγοράζει όσα κιλά ψάρια αυτή διαθέτει και αμέσως ξεκινά για την επόμενη τράτα (χωρίς να μεσολαβήσει χρόνος). Όμως, σε κάθε μονάδα του χρόνου μέχρι να φτάσει ο ταβερνιάρης, κάθε τράτα πουλάει ένα κιλό ψάρια σε τουρίστες που κάνουν βόλτα στην παραλία. Ζητείται να βρεθεί ο μέγιστος αριθμός κιλών ψαριών που μπορεί να αγοράσει ο ταβερνιάρης.

Αρχεία εισόδου

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

Αρχεία εξόδου

Η έξοδος πρέπει να αποτελείται από μία γραμμή που να περιέχει ακριβώς έναν ακέραιο αριθμό: το μέγιστο αριθμό κιλών ψαριών που μπορεί να αγοράσει ο ταβερνιάρης.

Παράδειγμα αρχείων εισόδου - εξόδου

phishboats.in	phishboats.out
3 20 8 -2 1	41

Περιορισμοί

• \(1 ≤ N ≤ 300\).
• \(1 ≤ M ≤ 1.000.000\).
• \(-10.000 ≤ X_i ≤ 10.000\).
• Όριο χρόνου εκτέλεσης: \(1\) sec.