Maşın İşləri
Siz Təsadüfi Kompleks Maşınlar (ACM) şirkətinin direktorusunuz, qabaqcıl texnologiyalardan istifadə edərək inkişaf etmiş maşınlar istehsal edən bir şirkət. Köhnə istehsal maşınları sıradan çıxıb, buna görə də şirkət üçün yeni istehsal maşınları almalısınız. Məqsədiniz yenidən qurma dövründə mümkün qədər çox pul qazanmaqdır. Bu dövr ərzində maşın alıb-sata və ACM-in mülkiyyətində olduğu müddətdə onları işlədə bilərsiniz. Məkan məhdudiyyətləri səbəbindən ACM eyni anda ən çox bir maşına sahib ola bilər.
Yenidən qurma dövründə satışda bir neçə maşın olacaq. Qabaqcıl maşınlar bazarında mütəxəssis olduğunuz üçün hər bir maşın M_i üçün qiymət P_i və mövcudluq günü D_i artıq bilirsiniz. Qeyd etmək lazımdır ki, əgər maşını M_i günü D_i almazsınızsa, o zaman başqa biri onu alacaq və o, daha sonra mövcud olmayacaq. Təbii ki, ACM-in maşının qiymətindən az pulu varsa, maşın ala bilməzsiniz.
Əgər D_i günü M_i maşınını alsanız, ACM onu D_i + 1 günündən işlədə bilər. Maşın işlədiyi hər gün şirkət üçün G_i dollar mənfəət gətirir.
Aldığınız hər hansı bir maşını hər hansı bir gündə satış qiymətinin bir hissəsini geri almaq üçün satmağa qərar verə bilərsiniz. Hər bir maşının bazara satıla biləcəyi bir satış qiyməti R_i var. Satış günündə maşını işlədə bilməzsiniz, lakin eyni gündə maşını satıb gəliri ilə yeni maşın ala bilərsiniz.
Yenidən qurma dövrü bitdikdən sonra ACM hələ də sahib olduğu hər hansı bir maşını satacaq. Sizin vəzifəniz ACM-in yenidən qurma dövründə qazandığı pulun miqdarını maksimuma çatdırmaqdır.
Giriş verilənləri
Giriş bir neçə test halından ibarətdir. Hər bir test halı üç müsbət tam ədəd N, C və D olan bir sətirlə başlayır. N satışda olan maşınların sayıdır (N ≤ 10^5), C şirkətin yenidən qurma dövrünə başladığı dollar miqdarıdır (C ≤ 10^9) və D yenidən qurmanın davam etdiyi günlərin sayıdır (D ≤ 10^9).
Növbəti N sətirin hər biri satışda olan bir maşını təsvir edir. Hər bir sətir dörd tam ədəd D_i, P_i, R_i və G_i ehtiva edir, müvafiq olaraq maşının satışda olduğu günü, alına biləcəyi dollar qiymətini, bazara satıla biləcəyi dollar qiymətini və maşının işlədilməsi ilə əldə olunan gündəlik mənfəəti göstərir. Bu ədədlər 1 ≤ D_i ≤ D, 1 ≤ R_i < P_i ≤ 10^9 və 1 ≤ G_i ≤ 10^9 şərtlərini təmin edir.
Son test halı üç sıfırdan ibarət bir sətirlə tamamlanır.
Çıxış verilənləri
Hər bir test halı üçün onun sıra nömrəsini və D+1 gününün sonunda ACM-in əldə edə biləcəyi ən böyük dollar miqdarını göstərin.
Nümunə çıxışın formatına əməl edin.