KiloBoom#519

KiloBoom

2 վայրկյան
512 մեգաբայթ
Very hard

Դուք խաղում եք ձեր սիրելի համակարգչային խաղը — 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 փորձի միավորներ: Այսպիսով, հիմնական փորձի ձեռքբերումը միավոր է մեկ վայրկյանում, և յուրաքանչյուր մակարդակի բարձրացման հետ, այն ավելանում է -ով:

Այնուամենայնիվ, կա խնդիր — ձեր ստեղնաշարը պարզապես կոտրվել է, և դուք չեք կարող շարժել ձեր հերոսին, և հետևաբար չեք կարող վերցնել թշնամիների թողած փորձի միավորները: Բախտի բերումով, դուք ունեք մագնիտ — յուրաքանչյուր մագնիտ, մի անգամ ակտիվացվելուց հետո, ներծծում է քարտեզի վրա առկա բոլոր փորձի միավորները և թույլ է տալիս հերոսին հավաքել դրանք՝ մակարդակը բարձրացնելու համար: Իհարկե, յուրաքանչյուր մագնիտ կարող է ակտիվացվել առավելագույնը մեկ անգամ, այնպես որ դուք պետք է օգտագործեք դրանք խելացիորեն:

Խաղի վերջնական նպատակը հնարավորինս շատ փորձի միավորներ հավաքելն է: Հաշվեք, թե որքան փորձի միավոր կարող եք ունենալ վայրկյանից հետո՝ մագնիտների օպտիմալ օգտագործմամբ:

Input

Մուտքի միակ տողը պարունակում է չորս ամբողջ թիվ 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) — խաղի տևողությունը, փորձի ձեռքբերման սահմանաչափերը և մագնիտների քանակը:

Output

Արտածեք մեկ ամբողջ թիվ — առավելագույն փորձի միավորը, որը կարող եք ձեռք բերել խաղի ավարտին:

Examples

Example 1

Loading
Loading

Example 2

Loading
Loading

Note

Առաջին փորձարկման դեպքում, դուք կարող եք օգտագործել մագնիտները -րդ և -րդ վայրկյանների հետո — տեսեք հետևյալ աղյուսակը:

Վայրկյաններ անցած

Օգտագործված մագնիտ

ոչ

ոչ

այո

ոչ

ոչ

ոչ

այո

Հավաքված ընդհանուր փորձ

Մակարդակ

Հավաքված փորձ

Փորձ մեկ վայրկյանում

Կարելի է ապացուցվել, որ հնարավոր չէ ավելի շատ փորձ ձեռք բերել խաղի ավարտին:

Երկրորդ փորձարկման դեպքում, դուք կարող եք պարզապես օգտագործել մեկ մագնիտ յուրաքանչյուր վայրկյանից հետո:

Վայրկյաններ անցած

Օգտագործված մագնիտ

ոչ

այո

այո

այո

այո

այո

այո

այո

այո

Հավաքված ընդհանուր փորձ

Մակարդակ

Փորձ մեկ վայրկյանում

Scoring

  1. ( միավոր): c = 0;

  2. ( միավոր): t \le 2 \cdot 10^3, m \le 3;

  3. ( միավոր): m,t \le 100;

  4. ( միավոր): t \le 2 \cdot 10^4;

  5. ( միավոր): լրացուցիչ սահմանափակումներ չկան: