Knjige

Ο Μάρκο βρέθηκε στην έκθεση βιβλίου Interliber όπου αγόρασε ~n~ βιβλία. Η ελκυστικότητα του ~i~-οστού βιβλίου, για τον Μάρκο, είναι ~k_{i}~. Ο Μάρκο ταξινόμησε τα βιβλία στο ράφι ανάλογα με την ελκυστικότητά τους, έτσι ώστε το πρώτο βιβλίο από αριστερά να είναι το λιγότερο ελκυστικό, και κάθε επόμενο προς τα δεξιά να είναι εξίσου ή περισσότερο ελκυστικό από το προηγούμενο.

Έχει περάσει αρκετός καιρός από την Interliber, αλλά ο Μάρκο μόνο τώρα βρήκε χρόνο για να διαβάσει τα βιβλία. Θα διαβάζει για συνολικά ~t~ λεπτά.

Για κάθε βιβλίο, μπορεί είτε να το διαβάσει ολόκληρο, πράγμα που του παίρνει ~a~ λεπτά, είτε να διαβάσει μόνο το περιεχόμενο από τα εξώφυλλα, πράγμα που του παίρνει ~b~ λεπτά.

Θα ξεκινήσει από το βιβλίο που βρίσκεται αριστερότερα. Αφού τελειώσει το τρέχον βιβλίο (είτε ολόκληρο είτε μόνο το περιεχόμενο από τα εξώφυλλα), προχωρά στο επόμενο βιβλίο, που είναι το πρώτο προς τα δεξιά από αυτό που μόλις διάβασε. Η έμπνευση που νιώθει ο Μάρκο είναι ίση με το άθροισμα των τιμών ελκυστικότητας των βιβλίων που έχει διαβάσει ολόκληρα. Ποια είναι η μέγιστη τιμή της έμπνευσης του Μάρκο μετά από ~t~ λεπτά;

Σημείωση: Αν ο Μάρκο ξεκινήσει να διαβάζει ένα βιβλίο αλλά δεν καταφέρει να το τελειώσει πριν από το τέλος των ~t~ λεπτών, αυτό το βιβλίο δεν συνεισφέρει στην έμπνευσή του.

Είσοδος

Η πρώτη γραμμή θα περιέχει τους ακέραιους αριθμούς ~n~, ~t~, ~a~ και ~b~ (~1 \le n \le 2 \cdot 10^{5},\;1 \le t \le 10^{9},\;1 \le b < a \le 10^{9})~, τον αριθμό των βιβλίων, τον χρόνο που θα αφιερώσει ο Μάρκο για ανάγνωση, τον χρόνο που τον χρόνο που απαιτείται για την ανάγνωση ενός βιβλίου και τον χρόνο που απαιτείται για την ανάγνωση του περιεχομένου από τα εξώφυλλα.

Η δεύτερη γραμμή θα περιέχει ~n~ ακεραίους ~k_{i}\;(1 \le k_{i} \le 10^{9},\;k_{i} \le k_{i+1})~, τις τιμές ελκυστικότητας των βιβλίων.

Έξοδος

Στην πρώτη και μοναδική γραμμή, εκτυπώστε τη μέγιστη έμπνευση που νιώθει ο Μάρκο μετά από ~t~ λεπτά.

Βαθμολογία

Υποπρόβλημα	Βαθμοί	Περιορισμοί
~1~	~7~	~k_{i} = k_{i+1}~ για κάθε ~i = 1, ... , n - 1~
~2~	~27~	~n \le 1000~
~3~	~36~	Κανένας επιπλέον περιορισμός

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

input

3 5 2 1
2 2 4

output

6

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

Για παράδειγμα, ο Μάρκο μπορεί να διαβάσει το πρώτο βιβλίο ολόκληρο, να διαβάσει μόνο το περιεχόμενο από το εξώφυλλο του δεύτερου βιβλίου και να διαβάσει το τρίτο βιβλίο ολόκληρο, επιτυγχάνοντας έτσι τη μέγιστη δυνατή έμπνευση.

input

2 10 3 1
3 3

output

6

input

4 10 3 2
3 4 5 6

output

12