Πρόβλημα

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

Η εταιρία Arch Bridges Construction (ABC) ειδικεύεται στην κατσκευή τοξοτών γεφυρών (τι περίεργο...). Αυτό το είδος γέφυρας υποστηρίζεται από κολώνες που συνδέουν την γέφυρα με το έδαφος. Τόξα μεταξύ των στήλων ισοκατανέμουν το βάρος της γέφυρας σε αυτές.

Οι γέφυρες της ABC συχνά έχουν έχουν άνιση απόσταση μεταξύ των γειτονικών στήλων. Για λόγους αισθητικής, οι γέφυρές τους έχουν πάντα ημικυκλικά τόξα (βλ. Σχήμα 1). Προφανώς, μία γέφυρα μπορεί να έχει τμήμα της που εφάπτεται στο έδαφος, αλλά όχι να συνεχίζει μέσα σε αυτό. Γι αυτό, μερικοί στήλοι είναι αδύνατο να χρησιμοποιηθούν.

Για δεδομένο προφίλ εδάφους και ζητούμενο ύψος γέφυρας ~h~ υπάρχουν πολλοί τρόποι να φτιάξουμε γέφυρα. Μοντελοποιούμε το προφίλ εδάφους ως μία τεθλασμένη γραμμή με ~n~ κορυφές της μορφής ~(x_1, y_1), (x_2, y_2), \dots , (x_n, y_n)~, όπου ~x_i~ είναι η θέση του σημείου κατά το μήκςο της γέφυρας και ~y_i~ το υψόμετρο του σημείου. Ο πρώτος και ο τελευταίος στήλος πρέπει να χτιστούν στα σημεία ~(x_1, y_1),\ (x_n, y_n)~ αντίστοιχα, ενώ οι υπόλοιποι στήλοι μπορούν να χτιστούν σε όποια κορυφή, αλλά όχι σε σημείο που δεν ανήκει σε αυτές.

Το κόστος της γέφυρας ισούται με το κόστων των στήλων (που είναι ανάλογο στο ύψος τους) συν το κόστος των τόξων (που είναι ανάλογο στην ποσότητα υλικού που χρησιμοποιήθηκε). Άρα, μία γέφυρα με ~k~ στήλους ύψους ~h_1, \dots h_k~ και μεταξύ τους αποστάσεις ~d_1, \dots, d_{k-1}~ κοστίζει συνολικά :

$$\displaystyle \alpha \cdot \sum_{i=1}^k h_i \ + \ \beta\cdot \sum_{i=1}^{k-1}d_i^2$$

για κάποιες δωσμένες σταθερές ~\alpha,\ \beta~. Η ABC θέλει να κατασκευάζει κάθε γέφυρα με τέτοιο τρόπο ώστε το κόστος της να ελαχιστοποιείται.

Μορφή Εισόδου

Η πρώτη γραμμή περιλαμβάνει 4 θετικούα ακεραίους ~n,h,\alpha,\beta~ όπου ~2 \leq n \leq 10^4~ είναι το πλήθος των κορυφών της τεθλασμένης, ~1 \leq h \leq 10^5~ είναι το επιθυμητό υψόμετρο της γέφυρας, ~1 \leq \alpha,\beta \leq 10^4~ οι σταθερές για τον υπολογισμό κόστους. Ακολουθούν ~n~ γραμμές, με την ~i~-οστή να περιέχει 2 ακεραίους ~0 \leq x_i \leq 10^5,\ 0 \leq y_i \leq h~, τις συντεταγμένες της ~i~-οστής κορυφής. (ισχύει ~x_1 < x_2 < \dots < x_n~).

Μορφή Εξόδου

Να εκτυπώσετε μοναδικό ακέραιο, το ελάχιστο κόστος για να κατασκευασθεί μία γέφυρα από το ~x_1~ έως το ~x_n~ και με υψόμετρο ~h~. Αν είναι αδύνατο, να εκτυπώσετε impossible.

Παράδειγμα 1

Είσοδος

5  60 18 2
0 0
20 20
30 10
50 30
70 20

Έξοδος

6460

Παράδειγμα 2

Είσοδος

4 10 1 1
0 0
1 9
9 9
10 0

Έξοδος

impossible