Maşın İşləri#2286
Siz İstənilən Dərəcədə Mürəkkəb Maşınlar (qısa adı ilə ACM) şirkətinin direktorusunuz. Şirkət qabaqcıl texnologiyalı avadanlıqlar istehsal edir və bunun üçün daha qabaqcıl istehsal maşınlarına ehtiyacı var. Köhnə istehsal maşınları xarab olub, buna görə şirkət üçün yeni istehsal maşınları almalısınız. Sizin məqsədiniz yenidənqurma dövründə mümkün qədər çox pul qazanmaqdır. Bu müddətdə siz maşın alıb sata, həmçinin ACM-ə məxsus olduqları müddətdə onları işlədərək gəlir əldə edə bilərsiniz. Yerlə bağlı məhdudiyyətlərə görə, ACM eyni anda ən çox bir maşına sahib ola bilər.
Yenidənqurma müddətində satışda bir neçə maşın olacaq. Qabaqcıl maşınlar bazarında ekspert olduğunuz üçün hər bir maşın M_i üçün satış qiyməti P_i və satışa çıxarıldığı gün D_i sizə əvvəldən məlumdur. Nəzərə alın ki, əgər M_i maşınını D_i günündə almasanız, başqa biri onu alacaq və onu daha sonra almaq mümkün olmayacaq. Təbiidir ki, ACM-in pulu çatmasa, heç bir maşını ala bilmərsiniz.
Əgər M_i maşınını D_i günündə alsanız, ACM onu D_i + 1 gündən işlətməyə başlaya bilər. Maşın işə salındıqdan sonra hər bir əməliyyat günü üçün şirkətə G_i dollar gəlir gətirir.
Aldığınız maşını istənilən bir gündə satıb, alış qiymətinin müəyyən bir hissəsini geri qaytara bilərsiniz. Hər bir maşının bazarda satıla biləcəyi qiymət R_i-dir. Maşını satış günündə işlədə bilməzsiniz, amma eyni gündə bir maşını satıb, onun puluna başqa maşın ala bilərsiniz.
Yenidənqurma müddəti bitdikdən sonra ACM sahib olduğu maşını satacaq. Sizin tapşırığınız, yenidənqurma müddətində ACM-in əldə edə biləcəyi maksimum pulu tapmaqdır.
Girişdə bir neçə test halı verilmişdir. Hər bir test halı bir sətirdə üç müsbət tam ədəd — , və ilə başlayır. satışda olan maşınların sayını göstərir (N \leq 10^5), şirkətin yenidənqurmaya başladığı dollar sayını (C \leq 10^9), isə yenidənqurma müddətinin gün sayını (D \leq 10^9) göstərir.
Növbəti sətrin hər biri satışda olan bir maşını təsvir edir. Hər sətrdə dörd tam ədəd — D_i, P_i, R_i və G_i verilir. Onlar müvafiq olaraq maşının satışa çıxarıldığı günü, alış qiymətini, bazara qaytarıla biləcəyi qiyməti və gündəlik gəlirini göstərir. Məlumatlar 1 \leq D_i \leq D, 1 \leq R_i < P_i \leq 10^9 və 1 \leq G_i \leq 10^9 şərtlərini ödəyir.
Sonuncu test halından sonra bir sətirdə üç sıfır verilir.
Hər bir test halı üçün onun nömrəsini və D+1 gününün sonunda ACM-in ola biləcəyi maksimum dollar miqdarını göstərin.
Nümunə çıxışdakı formata əməl edin.
Nümunə 1