24524번 - 아름다운 문자열

문제

당신은 문자열 $S$를 선물 받았다. 하지만 당신은 오직 문자열 $T$만을 아름답다고 생각하기 때문에 기쁘지 않다. 당신은 같은 종류의 문자가 두 번 이상 나오는 것을 질색하기 때문에, $T$ 역시 모든 문자가 서로 다르다.

그러던 당신에게 좋은 생각이 떠올랐다. 바로 $S$의 문자들을 골라내서 $T$를 만드는 것이다! 당신은 $S$에서 문자들을 골라내서 $S$에서의 순서대로 이어 붙여 새 문자열을 만드는 시행을 여러 번 반복할 수 있다. 이때 $S$의 각 문자는 최대 한 번씩 골라낼 수 있다. 예를 들어, $S$가 "aabb"이면 첫 번째 문자 "a"와 세 번째 문자 "b"를 골라 문자열 "ab"를 만들고, 다시 두 번째 문자 "a"와 네 번째 문자 "b"를 골라 문자열 "ab"를 만들 수 있다.

당신은 $T$를 가능한 한 많이 만들고 싶다. 만들 수 있는 $T$의 최대 개수를 구하는 프로그램을 작성해보자.

입력

첫째 줄과 둘째 줄에 영어 소문자로만 이루어진 문자열 $S$와 $T$가 각각 주어진다. $(1\leq \left|S \right|\leq 1,000円,000円;$ 1ドル\leq \left|T \right|\leq 26;$ $\left|T \right|\leq \left|S \right|)$

$T$의 모든 문자는 서로 다르다.

출력

첫째 줄에 만들 수 있는 $T$의 최대 개수를 출력한다.

제한

힌트