This page is still under construction.

Parts of this page are still being built. What you see may change.

String Decoration

Time limit2sMemory limit512 MB

Summary
Given a string S and N pattern strings, find the length of the shortest substring of S that contains every pattern as a substring.
Level

Hard8 of 10

Topics
String, Sliding window, String matching, Two pointers
Solved
No attempts yet

Problem

The year is 2019. The Ajou University algorithm club A.N.S.I. has finally been assigned a room!

The members of A.N.S.I. put their artistic spirit into decorating the new room, and Manyoung, who loves strings, wants to decorate the wall with a string. Since demand for this is rare, he could not find one, but then he found an online shop that sells substrings of a string S.

A substring is a contiguous part of the original string. For example, the substrings of "acka" are {"", "a", "c", "k", "ac", "ck", "ka", "ack", "cka", "acka"}, 10 in total.

While Manyoung was looking through S to decide which string would be good, some club members watching from behind began to name strings they wanted among the substrings of S.

  • Junseo (current president): "I would really like 'ansi' here to be included."
  • Junpyo (former president): "Oh, there's 'spectacle' over there too. I think 'spectacle' should be included as well."
  • Hyeonjeong (former former president): "Then let's put in this 'graduation' too."
  • ...
  • Jisu (current treasurer): "I don't care what it is, just please save some budget.."

Since Manyoung is a kind senior and cannot ignore their requests, he wants to buy a string that contains all of these strings as substrings. The price of a string is proportional to its length. For Jisu, who worries about the club budget, Manyoung wants to order the shortest substring of S that contains all the strings P1…PN wanted by the N club members as substrings. Find the length of the string Manyoung will order.

Input

The first line gives N. From the 2nd line to the N+1-th line, the length and the string of P1 through PN are given in order. Then the last line gives the length of S and S. All strings consist only of lowercase English letters from 'a' to 'z'.

S has P1…PN all as substrings.

Output

Print the minimum length of a substring of S that satisfies the condition on the first line.

Examples3

  1. Example 1

    Input
    4
2 an
4 anab
2 ab
4 nana
18 bananabananabanana
    Expected output
    5

  2. Example 2

    Input
    7
4 ajou
4 ajou
7 welcome
2 to
4 ajou
11 programming
7 contest
31 welcometoajouprogrammingcontest
    Expected output
    31

  3. Example 3

    Input
    2
7 insider
4 acka
53 superduperinsiderkinggodackaemperorgeneralchungmugong
    Expected output
    18