Задача . C. Феникс и распределение

У Феникса есть строка \(s\), состоящая из строчных букв латинского алфавита. Он хочет распределить все буквы своей строки по \(k\) непустым строкам \(a_1, a_2, \dots, a_k\) так, что каждая буква из \(s\) попадет ровно в одну из строк \(a_i\). Строки \(a_i\) не обязаны быть подстроками \(s\). Феникс может распределить буквы \(s\) и переупорядочить их внутри каждой строки \(a_i\) так как захочет.

Например, если \(s = \) baba и \(k=2\), Феникс может распределить буквы своей строки множеством способов, в том числе:

• ba и ba
• a и abb
• ab и ab
• bb и aa

Однако получить такие варианты он не может:

• baa и ba
• b и ba
• baba и пустая строка (\(a_i\) должны быть непустыми)

Феникс хочет разделить свою строку \(s\) на \(k\) строк \(a_1, a_2, \dots, a_k\) так, чтобы минимизировать лексикографически максимальную строку среди них, т. е. минимизировать \(max(a_1, a_2, \dots, a_k)\). Помогите ему найти оптимальное распределение и выведите минимально возможное значение \(max(a_1, a_2, \dots, a_k)\).

Строка \(x\) лексикографически меньше, чем строка \(y\), если либо \(x\) является префиксом \(y\) (и \(x \ne y\)), либо существует такой индекс \(i\) (\(1 \le i \le min(|x|, |y|))\), что \(x_i\) < \(y_i\) и для всех \(j\) \((1 \le j < i)\) \(x_j = y_j\). Здесь \(|x|\) обозначает длину строки \(x\).