คุณกำลังเล่นเกมและกำลังจะต่อสู้กับบอสลับ ในเกมนี้บอสไม่โจมตีคุณ แต่สามารถร่ายเวทฟื้นฟูได้
การต่อสู้มีทั้งหมด $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 เช่นเดิม