Problem2086--牛钢琴

2086: 牛钢琴

[Creator : ]
Time Limit : 1.000 sec  Memory Limit : 128 MB

Description

牛钢琴 

牛的钢琴从左往右有n个按键,第i个按键发出的“音调”是a[i]。

现在奶牛要弹奏一首长度是m个“音调”构成的的歌曲,歌曲的第i个“音调”必须是b[i]。

奶牛只使用1个手指弹琴,手指从第i个按键移动第j个按键需要花费|i-j|秒。

奶牛每次只能使用如下两种操作类型之一:

操作A:假如奶牛手指当前位置是i,那么它可以把手指移动到i-1或者i+1,而且钢琴对应的发出a[i-1]“音调”或者发出a[i+1]“音调”。

操作B:假如奶牛手指当前位置是i,那么它可以把手指移动到j,前提是a[i]等于a[j]。这个操作不会发出“音调”。



注意,任何时候,奶牛的手指移动到的位置范围都是1至N,不能超过钢琴的边界。

任务开始前,奶牛可以把手指放到任意一个按键。

你的任务是计算:奶牛至少需要多少秒完成任务。如果不可能完成任务则输出-1。



输入格式

第1行,两个整数: n和m。 1<=n,m<=300。

第2行,n个音调,第i个音调是a[i], 而且保证a[i]是一个小写英文字母。

第3行,m个音调,第i个音调是b[i], 而且保证b[i]是一个小写英文字母。



输出格式

一个整数。

输入/输出例子1

输入:

image.png

输出:

-1

输入/输出例子2

输入:

image.png

输出:

10

输入/输出例子3

输入:

image.png

输出:

5

样例解释

第3组测试数据解释:

奶牛一开始就把手指放到第7个位置,按下按键,钢琴发出“音调”:'b'。

然后使用两次操作A,都是向左移动,钢琴会发出两个“音调”: "oo"。

接着使用一次操作B,把手指移动到位置6, 然后使用两次操作A, 向左移动,钢琴会发出两个“音调”:“ok”音调 。

总共需要5秒。

Input

2 2
wa
ac

Output

-1

Sample Input Copy

7 7
monolog
nogolom

Sample Output Copy

10

HINT

m o n o l o g
n 0
o 1 1 3
g 4
o 9 7 5
l 6
o 9 7 7
m 10

Source/Category