24. Aqua Curtains in a Box

Difficulty: easy · String

Problem

A furnishing company makes curtains in two colours, aqua (`a`) and black (`b`). A batch of curtains is a string `str` of `a`s and `b`s. The curtains are packed in order into boxes of `L` curtains each; if the length is not a multiple of `L`, the leftover curtains go into one last, smaller box. The box with the most aqua curtains is labelled. Print the number of aqua curtains in the labelled box. For example, `bbbaaababa` with `L = 3` is packed as `bbb`, `aaa`, `bab`, `a`; the most aqua curtains in one box is 3.

Input

- Line 1: the string `str`. - Line 2: the integer `L`.

Output

Print the maximum number of `a`s in a single box.

Example 1

Input:
bbbaaababa
3
Output:
3

Explanation: Boxes: bbb, aaa, bab, a. The second box has 3 aqua curtains, the most.

Example 2

Input:
abbbaabbb
5
Output:
2

Explanation: Boxes: abbba, abbb. They hold 2 and 1 aqua curtains, so the answer is 2.

Constraints

- 1 <= |str| <= 10^5 - 1 <= L <= 10^5 - `str` contains only `a` and `b`

Solutions are judged against 2 sample and 10 hidden tests. Sign in to solve it · All problems