← 返回 citadel 的题目列表Maximum Earnings After Converting Days Off
类型：online_judge
An employee has a work schedule for the next n days, where schedule[i] is 1 for a workday and 0 for a day off.
Each workday earns a fixed amount, dailyPay.
A workday also earns an additional bonus if the previous day is a workday.
You may convert at most k days off (0) into workdays (1). You cannot convert workdays into days off.
Return the maximum total earnings.
Input Format
n k dailyPay bonus
schedule
1 <= n <= 2 * 10^5
0 <= k <= n
0 <= dailyPay, bonus <= 10^9
schedule is a binary string of length n.
Output Format
Print the maximum possible total earnings.
Example
Input:
5 1 10 5
10101
Output:
50
Example
Input
5 1 10 5
10101
Output
50