อะไรเชื่อมโยงพวกเราทุกคนเข้าด้วยกัน? บ่อยครั้งก็คือสะพาน ตั้งแต่สมัยโบราณ มนุษย์สร้างสะพานสำหรับถนน รถไฟ และคนเดินเท้า รวมทั้งสะพานส่งน้ำเพื่อขนส่งน้ำ นี่คือวิธีที่มนุษยชาติไม่ยอมจำนนต่อภูมิประเทศที่ไม่เอื้ออำนวย

บริษัท 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