Trapetsiya Şəkilli Yürüş Yolu
Arxa bağçanızda kiçik bir prefabrik çardaq qurmağı və onu arxa eyvanınıza bağlayan döşənmiş bir yol çəkməyi planlaşdırırsınız. Bu yolu yerli ev təmiri mağazasından alınan döşəmə daşları ilə tikəcəksiniz. Döşəmə daşları müxtəlif ölçülərdədir, lakin hamısı bərabəryanlı trapezoid formasındadır. Şəkil 1-in solunda göstərildiyi kimi, bərabəryanlı trapezoid, bərabəryanlı üçbucağın bir küncünü baza paralel olan bir xəttlə kəsdiyiniz zaman əldə edilən formadır. Belə bir döşəmə daşını üç parametr ilə təsvir edə bilərik: paralel kənarlarından birinin uzunluğu, a, digər paralel kənarın uzunluğu, b, və bu kənarların arasındakı perpendikulyar məsafə, h.
Şəkil 1: Bərabəryanlı trapezoid forması (sol), yol nümunəsi (mərkəz) və birləşmə tələbləri (sağ)
Yolu döşəmə daşlarının paralel kənarlarını birləşdirərək tikəcəksiniz, bir paralel kənar başlanğıcda arxa eyvana, digəri isə çardağa toxunacaq. Yolunuzun gözəl görünməsini istəyirsiniz, buna görə də Şəkil 1-in sağında göstərilən vəziyyətlərə icazə verməyəcəksiniz. İki döşəmə daşı birləşdiyi yerdə, onların kənarları tam olaraq eyni uzunluqda olmalıdır. Eyni şəkildə, bir döşəmə daşı arxa eyvana və ya çardağa toxunduğu yerdə, onun kənarı tam olaraq eyni uzunluqda olmalıdır. Xoşbəxtlikdən, ev təmiri mağazanızda müxtəlif trapezoid formalı döşəmə daşlarının geniş seçimi var, buna görə də bu tələblərə cavab verən bir yol tikə biləcəyinizə əminsiniz.
Döşəmə daşlarının qiyməti hər kvadrat santimetr səth sahəsi üçün iki sentdir. Böyük bir arxa bağçanız var, buna görə yolunuzun nə qədər uzun olmasına əhəmiyyət vermirsiniz. Sadəcə ən ucuz olanını istəyirsiniz.
Giriş verilənləri
Giriş bir neçə test halından ibarət olacaq. Hər test halı mövcud olan müxtəlif döşəmə daşlarının sayını göstərən müsbət tam ədəd, n, ilə başlayacaq. n dəyəri ən azı 1 və ən çox 1000 olacaq. Növbəti n sətir hər bir daş növünü onun tərəflərinin uzunluqlarını, a, b və sonra h verərək təsvir edəcək. Bu üç dəyər müsbət tam ədədlər olacaq, santimetrlərlə ölçüləcək və 1000-dən böyük olmayacaq. İki daş növü eyni deyil, lakin ev təmiri mağazanızda çoxlu döşəmə daşları var, buna görə də ehtiyacınız qədər hər növdən ala bilərsiniz. Hər bir test halının son sətiri yolun başlayacağı arxa eyvanın eni və yolun bitəcəyi çardağın kənarının enini verir. n üçün sıfır dəyəri bütün test hallarının sonunu göstərəcək.
Çıxış verilənləri
Hər bir test halı üçün tələblərinizə cavab verən ən ucuz yolun ümumi qiymətini dollarla çap edin. Belə bir yol tikmək həmişə mümkün olacaq.