Siz sevdiyiniz kompüter oyununu oynayırsınız — KiloBoom.
Bu oyunda, siz canavarlara qarşı mübarizə aparan bir qəhrəman rolunu oynayırsınız. Canavarları məğlub etdikdən sonra onlar təcrübə xalları düşür, və bu xalları toplayaraq qəhrəmanınızın səviyyəsini artıra bilərsiniz. Oyun zamanı qəhrəmanın səviyyəsi aşağıdakı kimi hesablanır: indiyə qədər toplanmış təcrübə xallarının cəmi olsun, onda l=0 əgər s=0-dır, əks halda l = \lfloor \log_2 (s) \rfloor ^\dagger. Başqa sözlə, "Səviyyəni Artırmaq" üçün xallarınızı ikiqat artırmalısınız.
^\dagger \lfloor \log_2 (x) \rfloor 2^k \le x olan ən böyük tam ədəd -ya bərabərdir. Məsələn, \lfloor \log_2 (23) \rfloor = 4, \lfloor \log_2 (8) \rfloor = 3.
Oyun saniyə davam edir, və hər saniyədən sonra mübarizə apardığınız canavarlar l \cdot c + k təcrübə xalları düşür. Bu şəkildə, əsas təcrübə qazanma xal/saniyədir, və hər Səviyyə Artımında, bu ilə artır.
Ancaq bir problem var — klaviaturanız sıradan çıxıb, qəhrəmanınızı hərəkət etdirə bilmir və buna görə də düşən təcrübə xallarını toplaya bilmir. Xoşbəxtlikdən, sizdə maqnit var — hər maqnit aktivləşdirildikdə, xəritədəki bütün təcrübə xallarını özünə çəkir və qəhrəmanın onları toplayaraq Səviyyə Artımına imkan tanıyır. Əlbəttə ki, hər maqnit ən çox bir dəfə aktivləşdirilə bilər, buna görə də onları ağıllı istifadə etməlisiniz!
Oyun məqsədi mümkün qədər çox təcrübə xalı toplamaqdır. Maqnitlərin optimal istifadəsi ilə saniyədən sonra əldə edə biləcəyiniz maksimum təcrübə xalı sayını müəyyən edin.
Girişdə yalnız dörd tam ədəd t, c, k, m (1 \le t \le 10^9; 0 \le c \le 10^5; 1 \le k \le 10^5; 1 \le m \le 10^9) — oyunun müddəti, təcrübə qazanma üçün sabitlər və maqnitlərin sayı.
Bir tam ədəd çıxarın — oyunun sonunda əldə edə biləcəyiniz maksimum təcrübə xalı.
Example 1
Example 2
Birinci test nümunəsində, siz -ci və -cı saniyələrdən sonra maqnitləri istifadə edə bilərsiniz — aşağıdakı cədvələ baxın:
Keçən saniyələr | |||||||
İstifadə olunan maqnit | yox | yox | bəli | yox | yox | yox | bəli |
Toplanmış ümumi təcrübə | |||||||
Səviyyə | |||||||
Toplanmamış təcrübə | |||||||
Saniyəyə düşən təcrübə |
Oyun bitdikdə daha çox təcrübə qazanmağın mümkün olmadığını göstərmək olar.
İkinci test nümunəsində, siz sadəcə hər saniyədən sonra bir maqnit istifadə edə bilərsiniz:
Keçən saniyələr | |||||||||
İstifadə olunan maqnit | yox | bəli | bəli | bəli | bəli | bəli | bəli | bəli | bəli |
Toplanmış ümumi təcrübə | |||||||||
Səviyyə | |||||||||
Saniyəyə düşən təcrübə |
( xal): c = 0;
( xal): t \le 2 \cdot 10^3, m \le 3;
( xal): m,t \le 100;
( xal): t \le 2 \cdot 10^4;
( xal): əlavə məhdudiyyət yoxdur.