Anda sedang bermain gim dan akan melawan bos rahasia. Dalam gim ini, bos tidak menyerang Anda, tetapi dapat merapalkan mantra regenerasi.

Pertarungan terdiri dari tepat $N$ ronde. Pada setiap ronde, tindakan berikut dapat terjadi dengan urutan ini:

1. Bos dapat memilih merapalkan mantra “Regenerasi”.
2. Anda dapat memilih merapalkan mantra “Racun” jika masih memiliki mana.
3. Anda menyerang dengan pedang, memberikan $X$ kerusakan.
4. Semua efek pasif diterapkan.

Ada dua jenis efek pasif: regenerasi dan racun. Efek-efek ini dapat bertumpuk, sehingga keadaan bos saat ini dijelaskan oleh tiga bilangan bulat: poin kesehatan saat ini ($hp$), jumlah tumpukan racun ($p$), dan jumlah tumpukan regenerasi ($r$). Pada awal pertarungan, tidak ada tumpukan racun maupun regenerasi ($p=r=0$). Setiap tumpukan racun memberikan $P$ kerusakan, dan setiap tumpukan regenerasi memulihkan $R$ poin kesehatan.

Mantra-mantra memiliki efek berikut:

“Regenerasi”: menambah jumlah tumpukan regenerasi $r$ sebesar $1$.

“Racun”: menambah jumlah tumpukan racun $p$ sebesar $1$. Jika jumlah tumpukan regenerasi positif ($r>0$), kurangi jumlah tersebut sebesar $1$.

Setelah ronde, $hp$ berkurang sebesar $X+P\cdot p-R\cdot r$ (nilai ini dapat negatif jika bos memulihkan kesehatan lebih cepat daripada kerusakan yang Anda berikan).

Untuk setiap ronde, Anda tahu apakah bos akan merapalkan “Regenerasi”. Anda memiliki cukup mana untuk merapalkan “Racun” $K$ kali (Anda tidak harus menghabiskan seluruh mana). Berapa kerusakan total terbesar yang dapat Anda berikan kepada bos, dengan kata lain, nilai maksimum $hp_{start}-hp_{end}$? Anggap $hp_{start}=10^{1000}$, sehingga Anda tidak dapat benar-benar membunuh bos dalam $N$ ronde. Kesehatan bos dapat melebihi nilai awalnya (lihat contoh ketiga).

Masukan

Baris pertama berisi 5 bilangan bulat $N,X,R,P,K$ ($1\le N,X,R,P\le10^6$, $0\le K\le N$).

Baris kedua berisi string biner sepanjang $N$. Karakter ke-$i$ adalah 1 jika bos merapalkan “Regenerasi” pada awal ronde ke-$i$, dan 0 jika tidak.

Keluaran

Cetak satu bilangan bulat — kerusakan total terbesar yang dapat Anda berikan selama pertarungan.

Contoh

Masukan 1

2 1010 1 1 1
01

Keluaran 1

2021

Masukan 2

3 2 1 1 1
001

Keluaran 2

8

Masukan 3

10 1 10 40 1
1111111111

Keluaran 3

-40

Catatan

Perhatikan contoh pertama. Kita dapat merapalkan “Racun” paling banyak sekali. Lihat apa yang terjadi jika kita merapalkannya pada ronde pertama.

• Pada ronde pertama, kita merapalkan “Racun”, sehingga pada akhir ronde ada 0 tumpukan regenerasi dan 1 tumpukan racun. Jadi $hp$ berkurang sebesar $X+P\cdot1-R\cdot0=1011$.

• Pada awal ronde kedua, bos merapalkan “Regenerasi”, sehingga pada akhir ronde ada 1 tumpukan regenerasi dan 1 tumpukan racun. Jadi $hp$ berkurang sebesar $X+P\cdot1-R\cdot1=1010$. Secara keseluruhan, kesehatan bos berkurang $1011+1010=2021$.

Sekarang lihat apa yang terjadi jika kita merapalkannya pada ronde kedua.

• Pada ronde pertama, tidak ada mantra yang digunakan, sehingga pada akhir ronde ada 0 tumpukan regenerasi dan 0 tumpukan racun. Jadi $hp$ berkurang sebesar $X+P\cdot0-R\cdot0=1010$.

• Pada awal ronde kedua, bos merapalkan “Regenerasi”, sehingga ada 1 tumpukan regenerasi. Lalu kita merapalkan “Racun”, mengurangi jumlah tumpukan regenerasi satu. Pada akhir ronde ada 0 tumpukan regenerasi dan 1 tumpukan racun. Jadi $hp$ berkurang sebesar $X+P\cdot1-R\cdot0=1011$. Secara keseluruhan, kesehatan bos kembali berkurang $1010+1011=2021$.

Jadi, kapan pun kita merapalkan “Racun” dalam contoh ini, kita tetap mengurangi kesehatan sebesar 2021.