أنت تلعب لعبة وتستعد لمقاتلة الزعيم السري. في هذه اللعبة لا يهاجمك الزعيم، لكنه يستطيع إلقاء تعاويذ التجدد.
يتكون القتال من $N$ جولة بالضبط. في كل جولة يمكن أن تحدث الأفعال التالية بهذا الترتيب:
- يمكن للزعيم اختيار إلقاء تعويذة «التجدد».
- يمكنك اختيار إلقاء تعويذة «السم» إذا بقيت لديك طاقة سحرية.
- تهاجم بالسيف، ملحقاً $X$ من الضرر.
- تُطبق جميع التأثيرات التلقائية.
يوجد نوعان من التأثيرات التلقائية: التجدد والسم. تتراكم التأثيرات، لذا توصف حالة الزعيم الحالية بثلاثة أعداد صحيحة: نقاط الصحة الحالية ($hp$)، وعدد طبقات السم الحالية ($p$)، وعدد طبقات التجدد الحالية ($r$). في بداية القتال لا توجد طبقات سم أو تجدد ($p=r=0$). تلحق كل طبقة سم $P$ من الضرر، وتستعيد كل طبقة تجدد $R$ نقطة صحة.
للتعاويذ التأثيرات التالية:
«التجدد»: يزيد عدد طبقات التجدد $r$ بمقدار $1$.
«السم»: يزيد عدد طبقات السم $p$ بمقدار $1$. إذا كان عدد طبقات التجدد موجباً تماماً ($r>0$)، ينقصه بمقدار $1$.
بعد الجولة تنخفض $hp$ بمقدار $X+P\cdot p-R\cdot r$ (قد تكون هذه القيمة سالبة إذا كان الزعيم يتعافى أسرع مما تلحق به الضرر).
تعرف لكل جولة ما إذا كان الزعيم سيلقي «التجدد». لديك طاقة سحرية كافية لإلقاء «السم» $K$ مرة (لا يلزم استخدام كل الطاقة). ما أكبر ضرر إجمالي تستطيع إلحاقه بالزعيم، أي ما القيمة القصوى لـ $hp_{start}-hp_{end}$؟ افترض أن $hp_{start}=10^{1000}$، لذا لا يمكنك قتل الزعيم فعلياً خلال $N$ جولة. قد تتجاوز صحة الزعيم قيمتها الأولية (انظر المثال الثالث).
الإدخال
يحتوي السطر الأول على 5 أعداد صحيحة $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$، $0\le K\le N$).
يحتوي السطر الثاني على سلسلة ثنائية بطول $N$. يكون الحرف رقم $i$ هو 1 إذا ألقى الزعيم «التجدد» في بداية الجولة $i$، و0 خلاف ذلك.
الإخراج
اطبع عدداً صحيحاً واحداً — أكبر ضرر إجمالي يمكنك إلحاقه خلال القتال.
أمثلة
الإدخال 1
2 1010 1 1 1 01
الإخراج 1
2021
الإدخال 2
3 2 1 1 1 001
الإخراج 2
8
الإدخال 3
10 1 10 40 1 1111111111
الإخراج 3
-40
ملاحظة
لننظر إلى المثال الأول. يمكننا إلقاء «السم» مرة واحدة على الأكثر. لنرَ ما يحدث إذا ألقيناه خلال الجولة الأولى.
خلال الجولة الأولى نلقي «السم»، لذا في نهايتها توجد 0 طبقة تجدد و1 طبقة سم. لذلك تنخفض $hp$ بمقدار $X+P\cdot1-R\cdot0=1011$ في هذه الجولة.
في بداية الجولة الثانية يلقي الزعيم «التجدد»، لذا في نهايتها توجد 1 طبقة تجدد و1 طبقة سم. لذلك تنخفض $hp$ بمقدار $X+P\cdot1-R\cdot1=1010$. إجمالاً انخفضت صحة الزعيم بمقدار $1011+1010=2021$.
لنرَ الآن ما يحدث إذا ألقينا التعويذة خلال الجولة الثانية.
خلال الجولة الأولى لا تُلقى أي تعويذة، لذا في نهايتها توجد 0 طبقة تجدد و0 طبقة سم. لذلك تنخفض $hp$ بمقدار $X+P\cdot0-R\cdot0=1010$.
في بداية الجولة الثانية يلقي الزعيم «التجدد»، فتوجد بعدها 1 طبقة تجدد. ثم نلقي «السم»، فننقص عدد طبقات التجدد بمقدار واحد. لذلك في نهاية الجولة توجد 0 طبقة تجدد و1 طبقة سم. وتنخفض $hp$ بمقدار $X+P\cdot1-R\cdot0=1011$. إجمالاً تنخفض صحة الزعيم مجدداً بمقدار $1010+1011=2021$.
إذن، مهما كان وقت إلقاء «السم» في هذا المثال، سنخفض الصحة بمقدار 2021.