אתם משחקים במשחק ועומדים להילחם בבוס הסודי. במשחק הזה הבוס אינו תוקף אתכם, אך הוא יכול להטיל לחשי התחדשות.

הקרב מורכב מבדיוק $N$ סיבובים. בכל סיבוב עשויות להתרחש הפעולות הבאות, בסדר הזה:

1. הבוס רשאי לבחור להטיל את לחש ״התחדשות״.
2. אתם רשאים לבחור להטיל את לחש ״רעל״ אם נשארה לכם מאנה.
3. אתם תוקפים בחרב וגורמים $X$ נזק.
4. כל ההשפעות הפסיביות מופעלות.

יש שני סוגי השפעות פסיביות: התחדשות ורעל. ההשפעות מצטברות, ולכן אפשר לתאר את מצבו הנוכחי של הבוס באמצעות שלושה מספרים שלמים: נקודות החיים הנוכחיות ($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.