CLARKSON

"Jeremy Clarkson Beatbox" is a YouTube montage in which the former Top Gear host appears to perform beatbox. Scenes from the show are cut apart and stitched back together into a single musical performance. The video went up in 2009 and has been watched almost three million times.

This year Jeremy Clarkson left the BBC after a disciplinary ruling. To commemorate the show, we want to build a sequel to that montage out of scenes from more recent episodes. The fans have already chosen the lyrics of the new video, but the editing is not easy.

No matter how skillfully the pieces are stitched together, viewers notice every transition. Two transitions that fall close together are irritating. The goal is to keep the transitions as far apart as possible, which is the same as making the shortest piece of the montage as long as possible.

You are given the lyrics of the song and the script of one episode. Cut the lyrics into consecutive pieces so that every piece occurs as a contiguous part of the script, maximize the length of the shortest piece, and print that length. If the lyrics cannot be built from the given script, print -1.

The first line contains the lyrics of the song and the second line contains the script of one episode. Both lines consist only of English uppercase and lowercase letters.

Print the length of the shortest piece in an optimal split, or -1 if no split exists.

Let $N$ be the length of the lyrics and $M$ the length of the script. $1 \le N \le 100000$ and $1 \le M \le 100000$. Uppercase and lowercase letters are different characters.

If the lyrics are JusticeAndTrust and the script is CarsAndTrucksAreJustNice, the lyrics split into Just, ice, AndTr, ust. Every piece occurs in the script, the lengths are 4, 3, 5 and 3, and the smallest of them is 3.