37ος ΠΔΠ B' Φάση
Μαγικό καζάνι (cauldron)

Τελικά ποιο είναι το μυστικό της επιτυχίας των πιτσών του Τάκη; Αν και ο ίδιος προσπαθεί να το κρατήσει κρυφό, η αλήθεια είναι ότι πρόκειται για την σάλτσα που φτιάχνει μέσα στο μαγικό καζάνι του.

Το βασικό συστατικό της σάλτσας είναι ο μαγικός ζωμός. Ο Τάκης έχει στο ντουλάπι του \(N\) βάζα που το καθένα περιέχει κάποια θετική ακέραια ποσότητα μαγικού ζωμού. Συγκεκριμένα, οι ποσότητες συμβολίζονται με \(w_1, w_2, \dots w_N\).

Για να παρασκευάσει σάλτσα, για αρχή ο Τάκης βάζει το καζάνι στη φωτιά και το γεμίζει με ποσότητα \(K\) από μαγικό νερό. Έπειτα, ανοίγει το ντουλάπι και διαλέγει κάποια βάζα, έτσι ώστε το άθροισμα των ποσοτήτων που περιέχουν να μην ξεπερνάει το \(K\). Στη συνέχεια, αδειάζει αυτά τα βάζα στο καζάνι, ένα ένα. Όταν ο Τάκης αδειάζει στο καζάνι ένα βάζο με ορισμένη ποσότητα μαγικού ζωμού, έστω \(w\), καταναλώνεται ποσότητα \(w\) μαγικού νερού και παράγεται ποσότητα \(w+c\) από σάλτσα. Το \(c\) είναι ένας ακέραιος αριθμός που παραμένει σταθερός καθ’ όλη την διάρκεια της παρασκευής και μπορεί να είναι είτε θετικός, είτε ίσος με το μηδέν, είτε αρνητικός, ενώ είναι εγγυημένο ότι για όλα τα βάζα ισχύει \(w+c\gt0\). Στο τέλος, ο Τάκης απομακρύνει το καζάνι από τη φωτιά και όλη η ποσότητα μαγικού νερού που έχει απομείνει, εφόσον έχει απομείνει, μετατρέπεται εξ’ ολοκλήρου σε σάλτσα.

Τι θα γίνει αν η πιτσαρία ξεμείνει από σάλτσα; Και μόνο η σκέψη ότι κάτι τέτοιο θα μπορούσε να συμβεί μια μέρα, ανησυχεί απίστευτα τον Τάκη. Για να τον καθησυχάσετε, υπολογίστε και θυμίστε του την μέγιστη ποσότητα σάλτσας που μπορεί να παρασκευάσει.

Πρόβλημα

Να αναπτύξετε ένα πρόγραμμα σε μια από τις γλώσσες του ΠΔΠ (PASCAL, C, C++, Java) το οποίο θα διαβάζει τα δεδομένα εισόδου από το αρχείο cauldron.in και θα εκτυπώνει τα αποτελέσματα στο αρχείο cauldron.out.

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

Η πρώτη γραμμή περιέχει τον αριθμό του υποπροβλήματος (βλ. παρακάτω). Η δεύτερη γραμμή περιέχει τρεις ακέραιους αριθμούς \(N\), \(K\) και \(c\) χωρισμένους ανά δύο με κενό διάστημα: το πλήθος των βάζων που διαθέτει ο Τάκης, την ποσότητα του μαγικού νερού που τοποθετεί στο καζάνι και την σταθερά για την παρασκευή, όπως περιγράφεται παραπάνω. Η τρίτη γραμμή αποτελείται από \(N\) ακέραιους αριθμούς \(w_1, w_2, \dots, w_N\), χωρισμένους ανά δύο με κενό διάστημα: τις ποσότητες μαγικού ζωμού που περιέχουν τα βάζα.

Δεδομένα εξόδου (cauldron.out):

Πρέπει να περιέχει μία μόνο γραμμή με έναν ακέραιο αριθμό: την μέγιστη ποσότητα σάλτσας που μπορεί να παρασκευάσει ο Τάκης.

Παράδειγμα εισόδου - εξόδου:

cauldron.in	cauldron.out
1 6 37 2 20 12 35 7 4 15	43

Εξήγηση: Ο Τάκης μπορεί να χρησιμοποιήσει το πρώτο, το δεύτερο και το πέμπτο βάζο. Με το πρώτο θα παράξει ποσότητα σάλτσας \(20+222\), με το δεύτερο \(12+214\) και με το πέμπτο \(4+26\). Θα έχει απομείνει ποσότητα \(1\) (\(37-20-12-4\)) απ’ το μαγικό νερό στο καζάνι, η οποία μετά θα μετατραπεί σε ποσότητα \(1\) από σάλτσα. Με αυτόν τον τρόπο, ο Τάκης παράγει συνολικά ποσότητα σάλτσας ίση με \(43\) (\(22+14+6+1\)) που είναι και η μέγιστη δυνατή.

Περιορισμοί:

\(1 \leq N \leq 200.000\).
\(1 \leq K \leq 1.000.000.000\).
\(1 \leq w_i \leq 1.000.000.000\).
Η απόλυτη τιμή του \(c\) δεν θα ξεπερνάει το \(1.000.000.000\).
Θα ισχύει ότι \(w_i+c\gt 0\), για κάθε \(i\) (\(1\leq i \leq N\)).

Υποπροβλήματα:

(17 βαθμοί) \(N\leq 20\)
(20 βαθμοί) \(c\leq 0\)
(30 βαθμοί) \(w_1=w_2=\cdots =w_N\)
(33 βαθμοί) Δεν υπάρχουν περαιτέρω περιορισμοί

Παρατηρήσεις:
Μορφοποίηση: Στην έξοδο, όλες οι γραμμές τερματίζουν με ένα χαρακτήρα newline.
Μέγιστος χρόνος εκτέλεσης: \(1\) sec.
Μέγιστη διαθέσιμη μνήμη: \(64\) MB.