CF101A.Homework

Once when Gerald studied in the first year at school, his teacher gave the class the following homework. She offered the students a string consisting of n small Latin letters; the task was to learn the way the letters that the string contains are written. However, as Gerald is too lazy, he has no desire whatsoever to learn those letters. That's why he decided to lose some part of the string (not necessarily a connected part). The lost part can consist of any number of segments of any length, at any distance from each other. However, Gerald knows that if he loses more than k characters, it will be very suspicious.

Find the least number of distinct characters that can remain in the string after no more than k characters are deleted. You also have to find any possible way to delete the characters.

有一次，杰拉尔德刚上小学一年级时，老师给全班布置了如下家庭作业：她给学生们提供了一个由 $n$ 个小写拉丁字母组成的字符串，任务是学会该字符串中所含字母的写法。然而，由于杰拉尔德非常懒惰，他根本不想学习这些字母。因此，他决定删去该字符串的一部分（不一定是连续的一段）。被删去的部分可以由任意数量、任意长度、彼此任意间隔的若干子串组成。但杰拉尔德知道，如果他删去的字符数超过 $k$ 个，就会显得非常可疑。

请找出：在最多删去 $k$ 个字符的前提下，字符串中可能剩余的最少的不同字符种类数。同时，还需给出一种可行的删去字符的具体方案。

The first input data line contains a string whose length is equal to n (1 ≤ n ≤ 105). The string consists of lowercase Latin letters. The second line contains the number k (0 ≤ k ≤ 105).

第一行输入数据包含一个长度为 $n$（$1 \leq n \leq 10^5$）的字符串，该字符串由小写拉丁字母组成。第二行输入数据包含一个整数 $k$（$0 \leq k \leq 10^5$）。

Print on the first line the only number m — the least possible number of different characters that could remain in the given string after it loses no more than k characters.

Print on the second line the string that Gerald can get after some characters are lost. The string should have exactly m distinct characters. The final string should be the subsequence of the initial string. If Gerald can get several different strings with exactly m distinct characters, print any of them.

第一行输出唯一的数字 $m$ —— 给定字符串在最多删除 $k$ 个字符后，可能剩余的最少不同字符个数。

第二行输出杰拉尔德在删除若干字符后可得到的字符串。该字符串应恰好包含 $m$ 个不同的字符，且必须是原字符串的一个子序列。若存在多个满足条件的字符串，输出任意一个即可。

In the first sample the string consists of five identical letters but you are only allowed to delete 4 of them so that there was at least one letter left. Thus, the right answer is 1 and any string consisting of characters "a" from 1 to 5 in length.

In the second sample you are allowed to delete 4 characters. You cannot delete all the characters, because the string has length equal to 7. However, you can delete all characters apart from "a" (as they are no more than four), which will result in the "aaaa" string.

In the third sample you are given a line whose length is equal to 8, and k = 10, so that the whole line can be deleted. The correct answer is 0 and an empty string.

在第一个样例中，字符串由五个相同的字母组成，但你最多只能删除其中的 4 个，以保证至少剩余一个字母。因此，正确答案是 1，且任意由 1 到 5 个字符 "a" 组成的字符串均为合法输出。

在第二个样例中，你最多可以删除 4 个字符。你不能删除全部字符，因为该字符串长度为 7。然而，你可以删除除 "a" 以外的所有字符（因为非 "a" 字符的数量不超过 4 个），从而得到字符串 "aaaa"。

在第三个样例中，给定字符串长度为 8，且 k = 10，因此整个字符串均可被删除。正确答案是 0，且输出为空字符串。