Maximize Earnings by Adding Working Days

Implement maximum_earnings(schedule, k, pay, bonus).

schedule is a string of 0 and 1, where 1 means a working day and 0 means a day off. You may change at most k zeroes into ones; existing working days cannot become days off.

Each working day earns pay. It also earns bonus if the immediately preceding day in this schedule is a working day after all changes. The first day has no preceding day within the schedule. Return the maximum total earnings over the full schedule.

For this interface, k is a nonnegative integer and pay and bonus are nonnegative integers in the same monetary unit. Represent these integers and the returned total using the decimal strings described below. You may use fewer changes than k, and cannot change more days off than exist. An empty schedule earns zero. No maximum schedule length or payment bound is specified.

Exact integer representation

This console represents integer values as canonical decimal strings so they retain their exact values in every supported language. This is an input/output representation convention; it does not impose a maximum integer magnitude.

• k, pay, and bonus are strings representing nonnegative integers. schedule remains the binary schedule string described above.
• Return the maximum earnings as a canonical decimal string. An empty schedule returns "0".
• A canonical nonnegative decimal string is "0" or a sequence of ASCII digits beginning with 1 through 9. It has no sign, leading zeroes, or whitespace.
• Earnings are exact integer amounts in the stated monetary unit. Do not use rounding, fixed-width overflow, or a remainder modulo another number.

Examples

maximum_earnings("101", "1", "10", "5") -> "40"

Changing the middle day gives three working days and two adjacent working-day pairs: 30 in base pay and 10 in bonuses.

maximum_earnings("000", "2", "10", "5") -> "25"

Two adjacent working days earn 20 in base pay and one bonus of 5. Separate working days would earn no adjacency bonus.