题目描述

小友在部门团建中参与了一款消消乐游戏，该游戏规则如下:

• 桌子上有一排动物图案，分别是猫"C"，狗"D"，狮子"L"，猴子"M"，鸟"B"。
• 小友的手里有一些对应的动物图案，小友的日标是清空桌子上的所有图案
• 每一回合，从小友手中的图案中任选一个，插入桌子的图案中，可以插入在两个图案之间或一排图案的两端
• 在插入图案之后，如果有出现三个或者三个以上图案相同且相连的情况，则将他们移除
• 如果移除图案后，再次出现三个或者三个以上图案相同且相连的情况，则可以继续移除这些图案，直到不再满条件
• 如果桌面上的图案均被移除，则认为小友获得了胜利
• 重复上述过程，直至图案全被移除或小友手中没有图案

给定两个字符串，分别表示桌面上初始图案排布情况和小友手里的图案，请你帮小友计算如果按照上还步骤移除桌面上所有的图案，所需要最少的图享数量，如果无法移除所有的图案，则返回-1

输入描述

输入共有两行

第一行表示桌面上初始图案分布排列情况

第二行表示小友手中图案情况

字符串均由“C”、“D”、“L”、“M”、“B”组成

输出描述

输出需要移除桌面上所有图案所需要最少的图案数量，若无法移除，则返回-1

样例

输入

BBCCLLBB
BCLCB

输出

2