Möhtəşəm körpülər#11345
Nə bizi hamımızı birləşdirir? Əlbəttə, bu tez-tez körpülərdir. Qədim zamanlardan bəri insanlar yollar, qatarlar, piyadalar üçün və suyun daşınması üçün akveduklar kimi körpülər tikiblər. Bu, insanlığın əlverişsiz coğrafiyanı cavab kimi qəbul etməməsinin bir yoludur.
Arch Bridges Construction (ABC) şirkəti, adından da göründüyü kimi, tağlı körpülərin tikintisi üzrə ixtisaslaşır. Klassik üslubda olan bu körpülər, körpünün altından çıxan sütunlarla dəstəklənir. Dayaq sütunları arasında olan tağlar körpünün ağırlığını qonşu dayaqlara paylayır.
ABC tərəfindən tikilən körpülər tez-tez qeyri-bərabər aralıqlarla yerləşdirilmiş dayaqlara malikdir. Estetik səbəblərdən ABC körpüləri həmişə yarımdairəvi tağlara malikdir, B.1 şəklində göstərildiyi kimi. Lakin, körpünün tağı yerə toxuna bilər, lakin yerin altına keçə bilməz. Bu, bəzi sütunların yerləşdirilməsini qeyri-mümkün edir.
Yer profilini və körpünün istənilən hündürlüyü nəzərə alaraq, adətən tağlı körpü tikmək üçün bir çox yollar mövcuddur. Biz yer profilini əsas nöqtələrlə təsvir olunan parça-parça xətti funksiya kimi modelləşdiririk (x_1, y_1), (x_2, y_2), ..., (x_n, y_n), burada nöqtənin koordinatı körpü boyunca mövqeyi, koordinatı isə körpünün həmin yerində dəniz səviyyəsindən yuxarı olan yerin hündürlüyüdür. İlk və son sütunlar birinci və sonuncu əsas nöqtələrdə tikilməlidir və hər hansı aralıq sütunlar yalnız bu əsas nöqtələrdə tikilə bilər. Körpünün dəyəri onun dayaqlarının dəyəri (onların hündürlüyü ilə mütənasibdir) və tağların dəyəri (istifadə olunan materialın miqdarı ilə mütənasibdir) ilə müəyyən edilir. Beləliklə, h_1, ..., h_k hündürlüyündə dayağa malik körpü, üfüqi məsafələrlə ayrılmış d_1, ..., d_{k -1} ümumi dəyəri
bəzi verilmiş sabitlər və üçün. ABC hər bir körpünü mümkün olan ən aşağı qiymətə tikmək istəyir.
Birinci sətir dörd tam ədəd n, h, α və ehtiva edir, burada n~(2 \le n \le 10^4) yer profilini təsvir edən nöqtələrin sayıdır, h~(1 \le h \le 10^5) körpünün dəniz səviyyəsindən istənilən hündürlüyüdür, və β~(1 \le α, β \le 10^4) əvvəllər təsvir edilən xərc əmsallarıdır. Sonra sətir gəlir, -ci sətir iki tam ədəd x_i, y_i~(0 \le x_1 < x_2 < ... < x_n \le 10^5 və 0 \le y_i < h) ehtiva edir, yer profilini təsvir edir.
Körpünün x_1 üfüqi mövqeyindən x_n mövqeyinə qədər dəniz səviyyəsindən hündürlükdə tikilməsinin minimal dəyərini çıxarın. Əgər belə bir körpü tikmək mümkün deyilsə, "impossible" çıxarın.
Nümunə 1
Nümunə 2