A bioinformatician needs to split a DNA sequence into valid gene segments. The DNA sequence contains only characters 'A', 'C', 'G', and 'T'.

A segment is valid if it matches one of the known gene patterns. You are given k known patterns.

Find the minimum number of segments needed to completely split the DNA sequence using only valid patterns. Patterns can be reused.

If the sequence cannot be completely split, return -1.

The first line contains the DNA sequence string s. The second line contains an integer k, the number of known patterns. The next k lines each contain a pattern string.

Print the minimum number of segments, or -1 if impossible.