空间限制：C/C++/Rust/Pascal 256 M，其他语言512 M
Special Judge, 64bit IO Format: %lld
题目描述
Ben's fortune predict system is successfully developed!
The predict system is a distributed system consists of computers. When it receives a predict request, each computer will generate one lower case letter as its output. The final fortune predict result is determined by the concentration of all
outputs.
Tired of getting good predictions like or
, Crystal decided to hack into the predict system and modify the predict result. He has already got the access permission of every computer in the predict system, so he could modify their output to any letter arbitrarily.
As Crystal is not going to take part in ICPC World Final 2077, he want unlucky predictions like . He found that the more substrings
occurs in the concentration of all
outputs, the unluckier he will get in the end. But as the contest is coming soon, he only has time to modify at most
outputs of the computers in the predict system.
As Crystal is busy hacking into the system, could you tell him how to get the most substrings after his modification?
输入描述:
The first line contains two integers
and
.
The second line contains a string of length
输出描述:
Output two lines. The first line contains a single integer, denotes the maximum number of
substring Crystal can get, after his modification. The second line contains the final modified predict string, if there are multiple ways that results in the maximum number of
Note that you don't have to minimize the number of
substring.