P16933 Ancient Scroll.

:::info[Problem Background] The battle is still going on. The hall deep inside the “Falling Star Archive” has long since lost its original appearance. Broken stone pillars lie toppled on the ground, and ancient bookshelves have been burned into black fragments by magical shockwaves, scattering everywhere. Dust and loose pages swirl in the chaotic airflow, like a silently burning snowfall. Black impacts tear the floor apart again and again, only to be cut off head-on by even brighter magic. The roar echoes layer after layer beneath the dome, shaking people until they can hardly breathe steadily. Even with the support of the mana-collecting stones, the situation still has not improved easily. The monster entrenched in the archive is simply too strong. It seems to have already merged with the remaining ancient magic of this place. The longer the fight drags on, the heavier and more dangerous its presence becomes. Fern’s ordinary attack magic can only barely keep the situation from collapsing completely. Stark has tried several times to get closer, but each time he is forced back by the terrible pressure spreading from the enemy. As for Frieren, although she still stands at the very front and her expression has not changed much, the deadlock of being unable to push the battle to an end is already enough to explain the problem. After another clash of spells, a brief gap finally appeared. Frieren gently took half a step back, her silver-white hair tips slightly floating in the aftershocks that had not yet calmed. She raised her eyes and looked at the monster still slowly approaching in front of the platform. For the first time, a thoughtful look appeared in her gaze, as if she had finally found an answer sealed away long ago in her memory. “If this continues, it will be troublesome.” she said softly. “Is there another way?” Fern asked at once. Frieren did not answer immediately. She simply reached into the inside of her robe and took out a very old ancient scroll. Its edges were dark yellow, and the patterns at the seal had been worn so much that they were hard to make out. Only the extremely ancient spell mark at the very center still gave off a calm yet dangerous feeling. It did not look like a spell that would be used casually in an ordinary fight. It was more like something left behind from a very, very long time ago, sleeping quietly in the depths of time, until it was awakened again now. “This is an ancient spell formula I collected before.” Frieren said calmly. “It should be very effective against this type of monster.” Stark looked at the scroll, but his expression did not relax much. “If it’s that effective, why didn’t you use it from the start?” “Because it’s not that simple.” Frieren gently unrolled the scroll, lowered her head, and glanced at the complex, ancient spell text on it. “The magic itself is not hard to control. The troublesome part is that, to make it work at its best, you need to use your brain a bit.” “Use my brain?” Fern froze slightly. “Yeah.” Frieren nodded. “Ancient mages always liked to design key spell formulas like this. Different combinations of formulas can produce magic of different strength. If you don’t combine them well, you still won’t be able to win. But if you can combine them properly, you can bring out the true power of ancient magic.” Her voice was still calm, but the monster in front clearly would not kindly give them much time to think. Black magic gathered again in the depths of the hall, like dark clouds pressing down before a storm. Fern subconsciously tightened her grip on her staff. Stark also steadied his stance again, standing in front of the two of them. Frieren, however, lowered her head and watched the spell patterns gradually appearing on the scroll, as if confirming some extremely subtle conditions that must not be mistaken. :::

The ancient scroll can be seen as a very long strip of paper, with a string $s$ written on it that contains only lowercase English letters, with length $n$. To best bring out the power of the ancient magic on the scroll, Frieren needs to pick **exactly $k$ continuous segments whose contents are completely identical** from this strip. Let the chosen content be the string $t$. The starting positions of these $k$ occurrences are $p_1 < p_2 < \cdots < p_k$. These $k$ segments may overlap each other. As long as their contents on the scroll are exactly the same, the choice is valid. **The same string appearing at different positions counts as different occurrences.** The higher the overlap of spell formulas, the greater the power. Frieren defines the “spell overprint score” as follows: - First, add up the lengths of these $k$ segments to get the spell overprint length $A = k|t|$. - Then, consider the **shortest continuous interval on the original scroll that covers these $k$ segments**. This interval starts at the beginning of the first chosen segment and ends at the end of the last chosen segment, giving the scroll length $B = p_k - p_1 + |t|$. Therefore, the “spell overprint score” of this choice is $A - B$. If Frieren thinks all plans are not worth it, she may also **choose nothing**. In that case, the “spell overprint score” is defined as $0$. Please find the maximum possible “spell overprint score”.

The first line contains two integers $n, k(1\leq n\leq 2\times 10^5, 1\leq k\leq 40)$, representing the length of the string $s$ on the scroll and the number of segments Frieren wants to pick. The second line contains a string $s$ of length exactly $n$, consisting only of lowercase English letters.

Output one line with one integer, representing the maximum possible “spell overprint score”.

For Sample 1, you can choose the segment `aba`, with positions $1$, $3$, and $5$. The spell overprint length is $3\times 3=9$, and the scroll length is $5 - 1 + 3 = 7$. Thus the “spell overprint score” is $2$. It can be proven that there is no better choice. For Sample 2, you can choose the segment `aaa`, with positions $1$, $2$, and $3$. The spell overprint length is $3\times 3=9$, and the scroll length is $3 - 1 + 3 = 5$. Thus the “spell overprint score” is $4$. It can be proven that there is no better choice. For Sample 3, you can choose the segment `a`, with positions $1$, $3$, $5$, and $7$. The spell overprint length is $4\times 1=4$, and the scroll length is $7 - 1 + 1 = 7$. Then the “spell overprint score” is $-3$. Clearly this plan is not worth it, so Frieren can choose nothing, and the “spell overprint score” is $0$. :::info[Problem Background] --- The final pattern on the ancient scroll finally lit up completely. In that instant, the hall that had been filled with black magic and roaring noise seemed to be suddenly pressed down by some even older, calmer power. Pale golden light slowly spread from the surface of the scroll, flowing inch by inch along Frieren’s staff into the fully constructed spell formula. It was not a dazzling light that people could not look at. Instead, it was so quiet that it felt almost solemn, like an echo coming from the far side of long years. Yet it was exactly this power that made the monster truly pause for the first time. “Now.” Frieren said softly. Fern immediately raised her hand and steadily sent the last bit of magic from the mana-collecting stones into a large amount of ordinary attack magic. Stark also clenched his teeth and forced his way in from the side, using all his strength to hold the monster’s movements in check. In the next moment, Frieren’s ancient magic fully descended. The huge yet condensed glow of the spell formula converged in the center of the hall into an almost straight line of light, and without hesitation, it pierced through the long-entrenched darkness. There was no piercing scream, only a deep, long reverberation. The dark red core in the monster’s chest shattered bit by bit within the light, and its pitch-black shell peeled away and collapsed as well, like a stone statue weathered for hundreds of years finally crumbling completely. The chaotic airflow swept up碎paper and stone dust across the floor. The remains of the bookshelves trembled slightly in the aftershocks, and then everything slowly quieted down. Only hurried breathing remained in the hall, gradually becoming steady. Fern lowered her staff, and her fingertips still carried a slight tremble. Stark braced himself with his weapon and let out a long breath, as if only now he could finally be sure the battle was over. Frieren simply watched quietly as the black residue in front of them dispersed, her expression still calm, as if she had finally dealt with an old matter that was somewhat troublesome. “It’s over.” she said softly. After a short time to pack up, the three did not stay there for long. Behind the shattered hall, a corridor leading deeper had quietly appeared in the dimness. There was no wind and no sound there, only faint magic silently flowing between the ancient stone walls. ::: Translated by ChatGPT 5