Դուք խաղում եք ձեր սիրելի համակարգչային խաղը — KiloBoom:
Այս խաղում, դուք խաղում եք որպես հերոս, ով պայքարում է հրեշների ալիքների դեմ: Հրեշները թողնում են փորձի միավորներ, երբ դուք հաղթում եք նրանց, և այս միավորները հավաքելով, դուք կարող եք բարձրացնել ձեր հերոսի մակարդակը: Խաղի ցանկացած պահի, հերոսի մակարդակը հաշվարկվում է հետևյալ կերպ. թող լինի մինչ այժմ հավաքված փորձի միավորների ընդհանուր քանակը, ապա l=0, եթե s=0, և l = \lfloor \log_2 (s) \rfloor ^\dagger այլապես: Այլ խոսքով, դուք պետք է կրկնապատկեք ձեր միավորները, որպեսզի «Բարձրացնեք մակարդակը»:
^\dagger \lfloor \log_2 (x) \rfloor հավասար է ամենամեծ ամբողջ թիվ , այնպես որ 2^k \le x. Օրինակ, \lfloor \log_2 (23) \rfloor = 4, \lfloor \log_2 (8) \rfloor = 3:
Խաղը տևում է վայրկյան, և յուրաքանչյուր վայրկյանից հետո, այն հրեշները, որոնց դեմ դուք պայքարում եք, թողնում են l \cdot c + k փորձի միավորներ: Այսպիսով, հիմնական փորձի ձեռքբերումը միավոր է մեկ վայրկյանում, և յուրաքանչյուր մակարդակի բարձրացման հետ, այն ավելանում է -ով:
Այնուամենայնիվ, կա խնդիր — ձեր ստեղնաշարը պարզապես կոտրվել է, և դուք չեք կարող շարժել ձեր հերոսին, և հետևաբար չեք կարող վերցնել թշնամիների թողած փորձի միավորները: Բախտի բերումով, դուք ունեք մագնիտ — յուրաքանչյուր մագնիտ, մի անգամ ակտիվացվելուց հետո, ներծծում է քարտեզի վրա առկա բոլոր փորձի միավորները և թույլ է տալիս հերոսին հավաքել դրանք՝ մակարդակը բարձրացնելու համար: Իհարկե, յուրաքանչյուր մագնիտ կարող է ակտիվացվել առավելագույնը մեկ անգամ, այնպես որ դուք պետք է օգտագործեք դրանք խելացիորեն:
Խաղի վերջնական նպատակը հնարավորինս շատ փորձի միավորներ հավաքելն է: Հաշվեք, թե որքան փորձի միավոր կարող եք ունենալ վայրկյանից հետո՝ մագնիտների օպտիմալ օգտագործմամբ:
Մուտքի միակ տողը պարունակում է չորս ամբողջ թիվ 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) — խաղի տևողությունը, փորձի ձեռքբերման սահմանաչափերը և մագնիտների քանակը:
Արտածեք մեկ ամբողջ թիվ — առավելագույն փորձի միավորը, որը կարող եք ձեռք բերել խաղի ավարտին:
Example 1
Example 2
Առաջին փորձարկման դեպքում, դուք կարող եք օգտագործել մագնիտները -րդ և -րդ վայրկյանների հետո — տեսեք հետևյալ աղյուսակը:
Վայրկյաններ անցած | |||||||
Օգտագործված մագնիտ | ոչ | ոչ | այո | ոչ | ոչ | ոչ | այո |
Հավաքված ընդհանուր փորձ | |||||||
Մակարդակ | |||||||
Հավաքված փորձ | |||||||
Փորձ մեկ վայրկյանում |
Կարելի է ապացուցվել, որ հնարավոր չէ ավելի շատ փորձ ձեռք բերել խաղի ավարտին:
Երկրորդ փորձարկման դեպքում, դուք կարող եք պարզապես օգտագործել մեկ մագնիտ յուրաքանչյուր վայրկյանից հետո:
Վայրկյաններ անցած | |||||||||
Օգտագործված մագնիտ | ոչ | այո | այո | այո | այո | այո | այո | այո | այո |
Հավաքված ընդհանուր փորձ | |||||||||
Մակարդակ | |||||||||
Փորձ մեկ վայրկյանում |
( միավոր): c = 0;
( միավոր): t \le 2 \cdot 10^3, m \le 3;
( միավոր): m,t \le 100;
( միավոր): t \le 2 \cdot 10^4;
( միավոր): լրացուցիչ սահմանափակումներ չկան: