KiloBoom#519

KiloBoom

ثانيتان
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. ( نقاط): لا قيود إضافية.