시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 422 99 93 30.195%

문제

감수성이 뛰어난 음유시인 영재는 일상생활 중에 번뜩 시상이 떠오르곤 한다.

하지만 기억력이 좋지 못한 영재는 시상이 떠오르면 그 순간 컴퓨터로 기록해야만 안 까먹는다! 시는 대문자, 소문자 알파벳과 빈칸으로 이루어져 있다. 시상은 매번 훌륭하지만 제목 짓는 센스가 부족한 영재는 시에 나오는 단어들의 첫 글자를 대문자로 바꾼 뒤 순서대로 이어서 제목으로 만든다. 만약 시의 내용이 'There is no cow level' 이라면 시의 제목은 'TINCL'이 된다.

시도 때도 없이 시를 기록하느라 낡아버린 영재의 키보드는 수명이 얼마 남지 않았다. 앞으로 스페이스 바와 영자판을 누를 수 있는 횟수가 정해져 있어 이를 초과하면 키보드가 수명이 다 하여 어떠한 작업도 하지 못하게 된다. 하나 다행인 점은, 키보드를 쓸 때 같은 문자가 연속으로 나오거나 빈칸이 연속으로 나오는 경우 영재는 자판을 꾹 눌러 한 번만 사용해서 키보드를 좀 더 효율적으로 쓸 수 있다. (A와 a는 다른 문자이므로 'Aa'는 2번의 a자판을 누른 것으로 한다.)

시의 내용과 시의 제목은 Enter 키로 구분된다. 다행히 Shift 키와 Enter 키는 항상 수명이 무한한 상황이다!

음유시인 영재가 이번에 지은 시의 내용과 스페이스 바와 영자판을 누를 수 있는 횟수가 주어졌을 때, 시의 내용과 제목을 모두 기록할 수 있다면 시의 제목을 출력하고, 만약 키보드의 수명이 다 하여 기록을 완벽하게 못 하게 된다면 -1을 출력하여라.

입력

첫 줄에 시의 내용이 주어진다.

둘째 줄에는 스페이스 바의 남은 사용 가능 횟수 주어진다.

셋째 줄에는 대소문자를 구별하지 않고, 26개의 알파벳에 대한 영자판의 남은 사용 가능 횟수가 알파벳순으로 주어진다.

출력

시의 내용과 제목을 모두 기록할 수 있다면 시의 제목을 출력하여라.

만약 키보드의 수명이 다 하여 기록을 완벽하게 못 하게 된다면 작업을 하지 못한다면 -1을 출력하여라.

제한

  • 시의 내용은 길이가 5,000을 넘지 않는 소문자, 대문자 알파벳과 빈칸으로 구성된 길이가 0보다 큰 문자열이다.
  • 시의 내용의 시작과 끝은 빈칸이 아닌 알파벳이 입력된다.
  • 스페이스바는 시의 내용을 입력할 때 외에는 사용하지 않는다.
  • 스페이스바와 영자판의 남은 사용 가능 횟수는 10,000보다 작거나 같은 음이 아닌 정수이다.

예제 입력 1

There is no cow level
5
1 0 2 0 4 3 0 1 2 0 0 3 0 2 2 0 4 1 1 2 0 1 1 0 0 0

예제 출력 1

TINCL

예제 입력 2

Show me the money
2
0 1 0 4 3 0 0 2 0 0 0 0 4 1 2 0 0 0 1 2 0 0 1 0 1 2

예제 출력 2

-1

예제 입력 3

show me the money
4
1 0 3 2 1 0 0 2 0 0 0 0 4 1 2 0 0 0 1 2 0 0 1 0 1 0

예제 출력 3

-1