Little Fabijan got bored with picture books, so he decided to read his first fairytale. Unfortunately, Fabijan often encounters a word that scares him. To overcome his fear, he will play a game he invented.
The scary word can be represented as an array of
He moves the finger to a position that is one place to the left or to the right of the current position, if that position exists. Also, Fabijan will then write the letter from the new position on the paper, after the last written letter.
He moves the finger to any position with the same letter as the current one. Fabijan will not write anything on the paper in this case.
It takes him
Fabijan will overcome his fear of the word if, at the end of the game, his favourite word is written on the paper. He wants to finish the fairytale as soon as possible, so he asks you to tell him the minimum number of seconds it will take him to overcome his fear of the given scary word.
Input Specification
The first line contains integers
The second line contains
The third line contains
Output Specification
Print the shortest possible time in seconds Fabijan needs to write his favourite word on the paper, or -1
if that is not possible.
Scoring
In test cases worth 20 points, letters in the word that scares Fabijan will be pairwise distinct.
Sample Input 1
2 2
wa
ac
Sample Output 1
-1
Sample Input 2
7 7
monolog
nogolom
Sample Output 2
10
Sample Input 3
14 5
niskoobrazovan
boook
Sample Output 3
5
Explanation for Sample Output 3
Fabijan will first put his finger on position b
. He will then move the finger
two times to the left, and each time write down the letter o
. In the next step, he will move the finger to position o
and k
. It took him five seconds in total, one second per move.
Comments