מה מחבר בין כולנו? ובכן, לעיתים קרובות אלו גשרים. מאז העת העתיקה אנשים בונים גשרים לכבישים, לרכבות ולהולכי רגל, וכן אמות מים להובלת מים. זו דרכה של האנושות שלא להיכנע לגאוגרפיה בלתי נוחה.

חברת Arch Bridges Construction ‏(ABC) מתמחה — ניחשתם נכון — בבניית גשרי קשת. סגנון הגשרים הקלאסי הזה נתמך בעמודים העולים מן הקרקע שמתחת לגשר. הקשתות שבין העמודים מחלקות את משקל הגשר בין העמודים הסמוכים.

דוגמה לגשר קשת רומי. מקור: Wikimedia Commons

בגשרים ש־ABC בונה, המרווחים בין העמודים אינם אחידים לעיתים קרובות. מטעמי אסתטיקה, הקשתות בגשרים של ABC הן תמיד חצאי מעגלים, כפי שמוצג באיור B.1. עם זאת, קשת הגשר רשאית לגעת בקרקע אך אינה רשאית להימשך אל מתחתיה. לכן חלק ממיקומי העמודים אינם אפשריים.

(a) עמודים עוקבים שמרחקם $d$ מחוברים בקשת חצי מעגלית שרדיוסה $r=d/2$.

(b) מיקום עמודים לא תקין (קשתות אינן רשאיות להימשך אל מתחת לקרקע).

(c) גשר המתאים לקלט לדוגמה 1.

איור B.1: דוגמאות לגשרים.

בהינתן פרופיל הקרקע וגובה הגשר הרצוי $h$, בדרך כלל יש דרכים רבות לבנות גשר קשת. אנו ממדלים את פרופיל הקרקע כפונקציה לינארית למקוטעין המתוארת באמצעות $n$ נקודות מפתח $(x_1,y_1),(x_2,y_2),\ldots,(x_n,y_n)$, כאשר קואורדינטת $x$ של נקודה היא המיקום לאורך הגשר, וקואורדינטת $y$ היא גובה הקרקע מעל פני הים במיקום זה. את העמוד הראשון והעמוד האחרון יש לבנות בנקודת המפתח הראשונה והאחרונה, בהתאמה, וכל עמוד ביניים יכול להיבנות רק בנקודות המפתח האלה. עלות גשר היא עלות העמודים שלו (הפרופורציונית לגובהם) ועוד עלות הקשתות שלו (הפרופורציונית לכמות החומר שבשימוש). לכן לגשר בעל $k$ עמודים שגובהיהם $h_1,\ldots,h_k$, המופרדים במרחקים אופקיים $d_1,\ldots,d_{k-1}$, יש עלות כוללת של

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

עבור קבועים נתונים $\alpha$ ו־$\beta$. חברת ABC רוצה לבנות כל גשר בעלות הנמוכה ביותר האפשרית.

קלט

השורה הראשונה של הקלט מכילה ארבעה מספרים שלמים $n,h,\alpha,\beta$, כאשר $n$ ‏($2\le n\le 10^4$) הוא מספר הנקודות המתארות את פרופיל הקרקע, $h$ ‏($1\le h\le 10^5$) הוא גובה הגשר הרצוי מעל פני הים, ו־$\alpha,\beta$ ‏($1\le\alpha,\beta\le 10^4$) הם מקדמי העלות שתוארו קודם. לאחר מכן מופיעות $n$ שורות, שבשורה ה־$i$ מהן שני מספרים שלמים $x_i,y_i$ ‏($0\le x_1<x_2<\ldots<x_n\le 10^5$ וגם $0\le y_i<h$), המתארים את פרופיל הקרקע.

פלט

הדפיסו את העלות המזערית לבניית גשר מן המיקום האופקי $x_1$ עד $x_n$ בגובה $h$ מעל פני הים. אם אי אפשר לבנות גשר כזה, הדפיסו impossible.

דוגמאות

קלט 1

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

פלט 1

6460

קלט 2

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

פלט 2

impossible