경의를 표하며

당신은 게임을 하고 있으며 비밀 보스와 싸우려 합니다. 이 게임에서 보스는 공격하지 않지만 재생 주문을 사용할 수 있습니다.

전투는 정확히 $N$ 라운드로 진행됩니다. 각 라운드에서는 다음 행동이 이 순서대로 일어날 수 있습니다.

1. 보스는 "재생" 주문을 사용할지 선택할 수 있습니다.
2. 마나가 남아 있다면 당신은 "독" 주문을 사용할지 선택할 수 있습니다.
3. 당신은 검으로 공격해 $X$의 피해를 줍니다.
4. 모든 지속 효과가 적용됩니다.

지속 효과에는 재생과 독 두 종류가 있습니다. 효과는 중첩되므로, 보스의 상태는 현재 체력 $hp$, 독 중첩 수 $p$, 재생 중첩 수 $r$ 세 정수로 나타납니다. 전투 시작 시 독 중첩과 재생 중첩은 모두 0입니다($p=r=0$). 독 중첩 하나는 $P$의 피해를 주고, 재생 중첩 하나는 체력을 $R$만큼 회복시킵니다.

주문의 효과는 다음과 같습니다.

"재생": 재생 중첩 수 $r$을 1 늘립니다.

"독": 독 중첩 수 $p$를 1 늘립니다. 재생 중첩 수가 양수($r > 0$)이면 $r$을 1 줄입니다.

라운드가 끝나면 $hp$는 $X + P \cdot p - R \cdot r$만큼 줄어듭니다. 보스의 회복이 피해보다 빠르면 이 값은 음수가 될 수 있습니다.

각 라운드에서 보스가 "재생"을 사용하는지는 미리 알고 있습니다. 당신은 "독" 주문을 $K$번 사용할 수 있는 마나가 있으며, 마나를 전부 쓸 필요는 없습니다. 보스에게 줄 수 있는 총 피해량의 최댓값을 구하세요. 즉 $hp_{start} - hp_{end}$의 최댓값입니다. $hp_{start} = 10^{1000}$으로 두므로 $N$ 라운드 안에 보스를 쓰러뜨릴 수는 없습니다. 보스의 체력이 처음 값보다 높아질 수도 있습니다(세 번째 예제 참고).

첫 줄에 정수 다섯 개 $N$, $X$, $R$, $P$, $K$ ($1 \le N, X, R, P \le 10^6$, $0 \le K \le N$)가 주어집니다.

둘째 줄에는 길이 $N$의 이진 문자열이 주어집니다. $i$번째 문자가 1이면 $i$번째 라운드 시작 시 보스가 "재생"을 사용하고, 0이면 사용하지 않습니다.

전투 중에 줄 수 있는 총 피해량의 최댓값을 정수 하나로 출력합니다.

첫 번째 예제를 보겠습니다. "독" 주문은 최대 한 번 사용할 수 있습니다. 첫 라운드에 독을 사용하면 그 라운드에 $X + P \cdot 1 - R \cdot 0 = 1011$만큼, 다음 라운드에 $X + P \cdot 1 - R \cdot 1 = 1010$만큼 체력이 줄어들어 합계는 2021입니다. 두 번째 라운드에 독을 사용해도 첫 라운드에 1010, 두 번째 라운드에 1011이 줄어 합계는 역시 2021입니다.