Frances has two great passions: programming and cross-stitching. Naturally, she eventually found a way to combine them.
She is working on a program to improve a long embroidery design. The design is represented by a string $$$b$$$, divided into sections by spaces. Each lowercase English letter represents the color of one stitch. For example, $$$p$$$ may represent pink, $$$g$$$ green, and $$$b$$$ blue; the actual colors are not important to Frances' program.
Frances has ten favorite embroidery patterns. Each pattern is represented by a string and has a beauty value:
| Pattern | Stitch pattern | Beauty |
| Tulip | pgr | 3 |
| Moon | byyb | 5 |
| Daisy | wwgyw | 7 |
| Cat | bwwbwb | 8 |
| Bow | prpb | 10 |
| Heart | prrb | 12 |
| Strawberry | rrggr | 14 |
| Sparkle | pywb | 17 |
| Butterfly | vpggpv | 20 |
| Bug | gpbrywvpg | 25 |
A section can be turned into one of Frances' patterns if both strings have the same length and differ in exactly one position. Frances can then replace the stitch at that position and gains the beauty value of the resulting pattern.
If a section is already exactly equal to any of Frances' favorite patterns, Frances leaves that section unchanged. It cannot be modified and gives no beauty points.
If a section can be turned into more than one pattern, Frances only considers the pattern with the highest beauty value.
Replacing stitches that are too close to each other may deform the fabric. Therefore, if Frances replaces stitches at absolute positions $$$p_1$$$, $$$p_2$$$, ..., the distance between any two selected positions must be at least $$$x$$$.
Positions are 0-indexed and refer to the complete string $$$b$$$. Spaces also occupy positions in the string, although a space can never be replaced.
Help Frances determine the maximum total beauty she can obtain.
The first line contains the string $$$b$$$, representing Frances' embroidery design.
The second line contains an integer $$$x$$$, the minimum allowed distance between any two stitches that Frances replaces.
A section is any maximal contiguous sequence of lowercase English letters in $$$b$$$.
The string $$$b$$$ contains only lowercase English letters ($$$a$$$–$$$z$$$) and spaces, and contains at least one lowercase English letter.
The following constraints hold:
$$$1 \le |b| \le 10^7$$$
$$$1 \le x \le 10^7$$$
The number of sections in $$$b$$$ does not exceed $$$10^6$$$.
Print one integer: the maximum total beauty Frances can obtain.
The answer fits in a signed 64-bit integer.
pyrb pgx6
17
pyrb pgx5
20
prrb pgx1
3
hello world4
0
In the first example, the section pyrb can be turned into:
Frances only considers Sparkle because it has the higher beauty value.
The section pgx can be turned into Tulip (pgr), worth $$$3$$$, by changing the stitch at absolute position $$$7$$$.
Therefore, the two candidate positions are $$$2$$$ and $$$7$$$. Their distance is $$$5$$$, which is smaller than $$$x = 6$$$, so Frances can choose only one modification. The maximum total beauty is $$$17$$$.
In the second example, the same candidate modifications occur at positions $$$2$$$ and $$$7$$$. Their distance is exactly $$$5$$$, so both modifications are allowed. Frances obtains $$$17 + 3 = 20$$$.
In the third example, the section prrb is already exactly equal to Heart. Frances leaves it unchanged, so it gives no beauty points and cannot be turned into another pattern. The section pgx can be turned into Tulip, giving $$$3$$$ beauty points.
In the fourth example, neither section can be turned into any of Frances' favorite patterns by replacing exactly one stitch.
