\(5^{th}\) round, March \(17^{th}\), 2012

Mirko‟s ASCII street is made of N lowercase letters of the English alphabet. The city government
occasionally replaces the tiles in the street. However, the letter tiles are in high demand, so the
government has only M different tile patterns available.
The i^{th} tile pattern consists of Li letters. A tile cannot be rotated or broken into pieces, and it can only
be placed such that the tile letters coincide with the contiguous letter subsequence in the street.
Tiles can overlap and we can use multiple tiles of the same pattern.
A street cell is untileable if it cannot be covered by any tile. Compute the number of untileable cells.

The first line of input contains the positive integer N (\(1 \le N \le 300\,000\)), the length of the street.
The second line of input contains N lowercase English letters, the letter sequence in the street.
The third line of input contains the positive integer M (\(1 \le M \le 5000\)), the number of tile patterns.
Each of the next M lines contains a description of a tile pattern with length Li (\(1 \le Li \le 5000\)). The tile
pattern descriptions consist of lowercase English letters.

The first and only line of output must contain the required number of untileable cells.

생성자가 기록되지 않았습니다.

출처 COCI 2011/2012 Contest 5