ما الذي يربطنا جميعًا؟ حسنًا، غالبًا ما تكون الجسور. منذ العصور القديمة، يبني الناس الجسور للطرق والقطارات والمشاة، وكذلك القناطر لنقل المياه. إنها طريقة البشرية في رفض الاستسلام لجغرافيا غير ملائمة.

تتخصص شركة 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