City Slogan

Limits: 2 sec., 256 MiB

This statement was translated automatically from Ukrainian.

In honor of the 47th day of the year, the Lviv City Hall decided to take a somewhat radical step — to change the city’s slogan. The new slogan, in the opinion of the City Hall, better describes the city’s connection to this ancient and important holiday.

The current city slogan is a string \(s\) consisting of uppercase English letters. The City Hall wants the new slogan to be the string \(t\). However, they understand that if they suddenly change the city’s slogan in a single day, terrible chaos will ensue. Perhaps even marshrutkas will stop running.

So they decided not to take risks and implement the changes gradually: in a single day, they can choose a subsequence of letters of the current slogan and delete them. Moreover, they cannot choose a subsequence that contains more than two identical letters. No other ways of modifying the slogan are allowed.

Note that a subsequence may contain letters that are not consecutive in the string.

Help the City Hall find the minimum number of days it takes to transform the slogan, or determine that it is impossible.

Input

The first line contains the initial slogan \(s\), and the second line contains the final slogan \(t\).

The strings contain only uppercase English letters.

Output

In a single line, output the minimum number of days, or -1 if achieving the goal is impossible.

Constraints

\(1 \le |s|, |t| \le 10^5\).

Samples