Bạn đang chơi một trò chơi và sắp chiến đấu với trùm bí mật. Trong trò chơi này, trùm không tấn công bạn nhưng có thể dùng phép hồi phục.
Trận đấu gồm đúng $N$ lượt. Trong mỗi lượt, các hành động sau có thể diễn ra theo thứ tự:
- Trùm có thể chọn dùng phép “Hồi phục”.
- Bạn có thể chọn dùng phép “Độc” nếu còn năng lượng phép.
- Bạn tấn công bằng kiếm, gây $X$ sát thương.
- Tất cả hiệu ứng bị động được áp dụng.
Có hai loại hiệu ứng bị động: hồi phục và độc. Các hiệu ứng cộng dồn, nên trạng thái hiện tại của trùm được mô tả bằng ba số nguyên: lượng máu hiện tại ($hp$), số tầng độc hiện tại ($p$) và số tầng hồi phục hiện tại ($r$). Ban đầu không có tầng độc hay hồi phục nào ($p=r=0$). Mỗi tầng độc gây $P$ sát thương, mỗi tầng hồi phục chữa $R$ máu.
Các phép có tác dụng sau:
“Hồi phục”: tăng số tầng hồi phục $r$ thêm $1$.
“Độc”: tăng số tầng độc $p$ thêm $1$. Nếu số tầng hồi phục dương ($r>0$), giảm số đó đi $1$.
Sau mỗi lượt, $hp$ giảm $X+P\cdot p-R\cdot r$ (giá trị này có thể âm nếu trùm hồi máu nhanh hơn bạn gây sát thương).
Bạn biết ở mỗi lượt trùm có dùng “Hồi phục” hay không. Bạn có đủ năng lượng để dùng “Độc” $K$ lần (không nhất thiết dùng hết năng lượng). Tổng sát thương lớn nhất bạn có thể gây lên trùm, tức giá trị lớn nhất của $hp_{start}-hp_{end}$, là bao nhiêu? Giả sử $hp_{start}=10^{1000}$, nên bạn không thể thực sự giết trùm trong $N$ lượt. Máu của trùm có thể vượt quá giá trị ban đầu (xem ví dụ thứ ba).
Dữ liệu vào
Dòng đầu chứa 5 số nguyên $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$, $0\le K\le N$).
Dòng thứ hai chứa xâu nhị phân dài $N$. Ký tự thứ $i$ là 1 nếu trùm dùng “Hồi phục” ở đầu lượt thứ $i$, và là 0 nếu không.
Dữ liệu ra
In ra một số nguyên — tổng sát thương lớn nhất bạn có thể gây trong trận đấu.
Ví dụ
Dữ liệu vào 1
2 1010 1 1 1 01
Dữ liệu ra 1
2021
Dữ liệu vào 2
3 2 1 1 1 001
Dữ liệu ra 2
8
Dữ liệu vào 3
10 1 10 40 1 1111111111
Dữ liệu ra 3
-40
Ghi chú
Xét ví dụ đầu tiên. Ta chỉ có thể dùng “Độc” nhiều nhất một lần. Hãy xem điều gì xảy ra nếu dùng ở lượt đầu.
Trong lượt đầu, ta dùng “Độc”, nên cuối lượt có 0 tầng hồi phục và 1 tầng độc. Vì vậy, $hp$ giảm $X+P\cdot1-R\cdot0=1011$.
Đầu lượt thứ hai, trùm dùng “Hồi phục”, nên cuối lượt có 1 tầng hồi phục và 1 tầng độc. Vì vậy, $hp$ giảm $X+P\cdot1-R\cdot1=1010$. Tổng cộng máu của trùm giảm $1011+1010=2021$.
Giờ hãy xem điều gì xảy ra nếu dùng phép ở lượt thứ hai.
Trong lượt đầu, không có phép nào được dùng, nên cuối lượt có 0 tầng hồi phục và 0 tầng độc. Vì vậy, $hp$ giảm $X+P\cdot0-R\cdot0=1010$.
Đầu lượt thứ hai, trùm dùng “Hồi phục”, tạo 1 tầng hồi phục. Sau đó ta dùng “Độc”, giảm số tầng hồi phục đi một. Cuối lượt có 0 tầng hồi phục và 1 tầng độc. Vì vậy, $hp$ giảm $X+P\cdot1-R\cdot0=1011$. Tổng cộng máu của trùm lại giảm $1010+1011=2021$.
Vậy trong ví dụ này, dù dùng “Độc” lúc nào, ta cũng làm máu giảm 2021.