Your friend has just accused you of having good gacha luck. To prove them wrong, you have been keeping track of the results of every gacha pull over the past few months in a spreadsheet. Specifically, your spreadsheet contains entries, each containing a value of either a or a . A value of in the -th entry denotes that the -th pull contained a 4 star card, and a denotes otherwise. The unluckiness score of a subsection (a contiguous subsequence) of these entries is calculated as follows:
- The score is initially set to be the number of s in the subsection.
- Then, for each in the subsection, the unluckiness score is halved without rounding.
- Finally, the score is set to be the smallest integer that is no smaller than its current value.
To refute their claim as effectively as possible, you will send them screenshots containing mutually disjoint subsections of your spreadsheet. What is the maximum possible total unluckiness score of the subsections in the screenshots?
Subtask 1 [1/15]
Subtask 2 [1/15]
Subtask 3 [2/15]
Subtask 4 [5/15]
Subtask 5 [3/15]
Subtask 6 [3/15]
No additional constraints.
The first line contains integers and .
The second line contains a binary string of length , representing the entries of the spreadsheet in order.
Output a single integer on its own line, the maximum possible total unluckiness score of the subsections.
9 2 001000100
One optimal solution would be to include the first entries in the first screenshot and the -th and -th entries in the second. These have unluckiness scores of and respectively, giving a total unluckiness score of .