모스 부호

모스 부호에서 각 글자는 점과 선의 나열로 표현된다. 하지만 이것만으로는 무선으로 글을 전송할 수 없다. 그래서 모스 부호는 점과 선의 길이, 그리고 요소 사이의 여러 쉼의 길이도 함께 정한다.

이 문제에서는 송신 측에서 모스 부호로 부호화한 디지털화된 무선 신호를 다룬다. 신호는 +와 -로 이루어진 문자열이다. 각 문자는 해당 시간 틱(tick)에 소리가 있었는지 나타낸다. +는 소리가 있었음을, -는 소리가 없었음을 뜻한다. 이 문제에서 모스 부호의 요소는 다섯 종류다. 요소는 다음 표에 따라 신호에 기록된다.

예를 들어 표준 라틴 모스 부호를 쓰면 두 단어 HELLO WORLD는 요소 63개, 틱 109개인 신호로 부호화된다.

두 단어 사이의 쉼은 5 틱이다. 신호의 앞과 뒤에는 쉼이나 특별한 요소가 없다.

자동 디지털화 과정에서는 오류가 생기기 쉬워서 신호를 해독하기 어렵다. 이 과정은 어떤 요소든 한 틱씩 짧게 하거나 길게 할 수 있다. 단, 한 틱짜리 요소는 더 짧아질 수 없다.

사전과 디지털화된 신호가 주어진다. 원래 텍스트가 다음 조건을 만족한다고 가정하고, 디지털화 과정이 저지른 오류의 최소 개수를 구한 뒤 원래 텍스트를 복원하라.

1. 원래 텍스트는 사전에 있는 단어만 포함한다.
2. 라틴 모스 부호를 사용한다.
3. 위에서 설명한 오류 외에 다른 오류는 없다.

첫 줄에는 두 정수 $M$(사전의 단어 수)과 $N$(신호의 틱 수)이 주어진다 ($1 \le M, N \le 5\,000$).

다음 $M$줄에는 사전의 단어가 한 줄에 하나씩 주어진다. 각 단어는 비어 있지 않으며 대문자 라틴 알파벳으로만 이루어진다. 모든 단어 길이의 합은 $5\,000$을 넘지 않는다.

나머지 줄에는 +와 -로 이루어진 디지털화된 신호가 주어진다. 신호의 총 길이는 $N$이다. 신호는 임의로 나뉘어 여러 개의 빈 줄이 아닌 줄로 주어질 수 있다. 신호에는 +가 적어도 하나 있다.

주어진 조건에서 신호를 만들 수 없으면 -1을 한 줄에 출력한다.

그렇지 않으면 첫 줄에 가능한 최소 오류 개수 $K \ge 0$을 출력한다. 둘째 줄에는 그 오류 개수로 신호를 만들 수 있는 원래 텍스트를 출력한다. 텍스트의 단어는 공백 하나로만 구분한다.

최소 오류 개수로 신호를 만드는 텍스트가 여러 개면 사전순으로 가장 작은 것을 출력한다. 공백은 모든 글자보다 작다.

첫 번째 예제는 문제 설명의 예시 그대로이며 오류가 없다. 두 번째 예제는 텍스트가 같지만, 요소 12개가 한 틱씩 짧아지거나 길어졌다. 세 번째 예제에는 11 틱짜리 쉼이 있는데, 이는 만들어질 수 없다. 가장 긴 요소는 단어 사이의 5 틱 쉼이며, 오류가 나면 6 틱이 될 수 있다. 네 번째 예제에는 점이 다섯 개 있다. 이 점들로 E, I, S, H 글자를 여러 방식으로 조합할 수 있다. 하지만 사전에 있는 단어는 HELLO뿐이고, 이 단어는 이 글자들만으로 만들 수 없다.