Censorship

Interview

Time limit1sMemory limit128 MB

Summary

Given a text and a filter word set, remove occurrences repeatedly to make the shortest possible result and report its length.

Level: Hard8 of 10
Topics: Dynamic programming, String, Intervals
Solved: No attempts yet

Problem

As part of a new curriculum reform, the CS department has decided to censor its course texts. In this problem you must help the department by writing a program that eliminates from an input text every occurrence of the words in a filter set.

Formally, a word $w$ can be removed from a string $s$ whenever $w$ is a substring of $s$ (the characters of $w$ appear consecutively in $s$ ). Given a text string $s$ and a set $T$ of filter words, return the length of the shortest string that can result from iteratively removing words of $T$ from $s$ . Each word in $T$ may be removed any number of times, and removing one word can make new occurrences appear.

Input

The input contains multiple test cases. Each test case begins with an integer $n$ ( $1 \le n \le 50$ ), the size of the filter set $T$ , followed by the text string $s$ , followed by the $n$ filter words $t_1, \dots, t_n$ . The text string and every filter word consist only of the lowercase letters 'a' through 'z' and have length between $1$ and $50$ . All filter words within a test case are distinct. Input is terminated by a line containing a single $0$ , which must not be processed.

Output

For each test case, print a single integer: the minimum possible length of the resulting string.

Hint

[…] marks the word removed at each step, and ∅ denotes the empty string.

c[cde]defcde → [cde]fcde → f[cde] → f
[aa]baab → [ba]ab → [ab] → ∅
[aa]baab → b[aa]b → [bb] → ∅

Examples3

Example 1

Input

1 ccdedefcde cde
3 aabaab aa ba ab
3 aabaab aa ba bb
0

Expected output

1
0
0

Example 2
Input
```
1 abc xyz
0
```
Expected output
```
3
```
Example 3
Input
```
1 aaaa aa
0
```
Expected output
```
0
```