牛的钢琴从左往右有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
输入:
输出:
10
输入:
输出:
5
第3组测试数据解释:
奶牛一开始就把手指放到第7个位置,按下按键,钢琴发出“音调”:'b'。
然后使用两次操作A,都是向左移动,钢琴会发出两个“音调”: "oo"。
接着使用一次操作B,把手指移动到位置6, 然后使用两次操作A, 向左移动,钢琴会发出两个“音调”:“ok”音调 。
总共需要5秒。
7 7
monolog
nogolom
10
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 |