L. Coding in Stitches
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

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:

PatternStitch patternBeauty
Tulippgr3
Moonbyyb5
Daisywwgyw7
Catbwwbwb8
Bowprpb10
Heartprrb12
Strawberryrrggr14
Sparklepywb17
Butterflyvpggpv20
Buggpbrywvpg25

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.

Input

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$$$.

Output

Print one integer: the maximum total beauty Frances can obtain.

The answer fits in a signed 64-bit integer.

Examples
Input
pyrb pgx
6
Output
17
Input
pyrb pgx
5
Output
20
Input
prrb pgx
1
Output
3
Input
hello world
4
Output
0
Note

In the first example, the section pyrb can be turned into:

  • Heart (prrb), worth $$$12$$$, by changing the stitch at absolute position $$$1$$$;
  • Sparkle (pywb), worth $$$17$$$, by changing the stitch at absolute position $$$2$$$.

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.