Holding

Δύσκολες στιγμές περιμένουν τον Ivica και την Holding του – ένας όμιλος ~N~ εταιρειών της Κροατίας που είναι στην ιδιοκτησία του. Κάθε μία από αυτές τις εταιρείες έχει χρέη, οπότε το κράτος έστειλε δικούς του δικηγόρους να του τα πάρουν όλα. Έχουμε ανακαλύψει ότι ο Ivica κατάφερε να κάνει μια συμφωνία με το κράτος για να του αφήσει ορισμένες εταιρείες παρά το τεράστιο χρέος. Ποια από όλες; Το ανακαλύψαμε και αυτό.

Οι κρατικοί δικηγόροι κατέθεσαν ~N~ έγγραφα ιδιοκτησίας των εταιρειών του Ivica πάνω στο τραπέζι. Το χρέος της πρώτης εταιρείας αναγράφεται στο πρώτο χαρτί ~A_1~, το χρέος της δεύτερης εταιρείας γράφεται στο ~A_2,\;\ldots~ και το χρέος της τελευταίας εταιρείας γράφεται στο τελευταίο χαρτί ~A_N~. Ο Ivica έκανε συμφωνία με το κράτος για να αποχωρήσει από τις εταιρείες ~A_L,\;A_{L+1},\;\ldots,\;A_R~, όπου τα ~L~ και ~R~ αντιπροσωπεύουν τις θέσεις σε μια σειρά από χαρτιά στο τραπέζι. Ευτυχώς για τον Ivica, οι δικηγόροι είναι (επίσης) διεφθαρμένοι. Θα τον αναγκάσουν να πάρει τον ίδιο συνεχόμενο υποπίνακα, όπως συμφωνήθηκε (από ~L~ στο ~R~ χαρτί), αλλά θα τον αφήσουν να ανταλλάξει οποιαδήποτε δύο χαρτιά στον πίνακα για συγκεκριμένο κόστος. Πιο συγκεκριμένα, η ανταλλαγή χαρτιών στις θέσεις ~i~ και ~j~ θα του κοστίσει ~|i - j|~ kunas (νόμισμα της Κροατίας). Ο Ivica είναι απελπισμένος. Έχει μόνο ~K~ kunas στην τσέπη του που τώρα θέλει να ξοδέψει με τέτοιο τρόπο ώστε το άθροισμα των χρεών των εταιρειών που του μένει να είναι όσο το δυνατόν μικρότερο.

Βοηθήστε τον Ivica να πετύχει τον στόχο του.

Είσοδος

Η πρώτη γραμμή περιέχει τέσσερις ακέραιους ~N,\;L,\;R~ ~(1 \le L \le R \le N \le 100)~ και ~K~ ~(0 \le K \le 10\,000)~ χωρισμένους με κενό διάστημα.

Η δεύτερη γραμμή περιέχει ~N~ ακέραιους ~A_i\;(0 \le A_i \le 10^6)~ από την περιγραφή της εργασίας.

Έξοδος

Θα πρέπει να βγάλετε έναν μεμονωμένο ακέραιο αριθμό που αντιπροσωπεύει το μικρότερο ποσό του συνολικού χρέους που θα έχει ο Ivica εάν έχει ξοδεύει βέλτιστα τα ~K~ kunas του.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
1	22	~N \le 13~ και ~R = N~
2	33	~N \le 50~ και ~R = N~
3	33	~N \le 50~
4	22	Κανένας επιπλέον περιορισμός.