题目内容

给定两个字符串，分别为字符串 $A$ 与字符串 $B$。

例如 $A$ 字符串为 "ABCABBA"，$B$ 字符串为 "CBABAC"，可以得到下图 $m \times n$ 的二维数组，定义原点为 $(0,0)$，终点为 $(m,n)$，水平与垂直的每一条边距离为 $1$，映射成坐标系如下图。

从原点 $(0,0)$ 到 $(0,A_1)$ 为水平边，距离为 $1$，从 $(0,A_1)$ 到 $(1,C_1)$ 为垂直边，距离为 $1$；

假设两个字符串同一位置的两个字符相同，则可以作一个斜边，如 $(1,C_1)$ 到 $(2,B_1)$ 最短距离为斜边，距离同样为 $1$。

作出所有的斜边如下图，$(0,0)$ 到 $(B_k,B_k)$ 的距离为：$1$ 个水平边 $+$ $1$ 个垂直边 $+$ $1$ 个斜边 $= 3$。

根据定义可知，原点到终点的最短距离路径如下图红线标记，最短距离为 $9$：

输入描述

空格分割的两个字符串 $A$ 与字符串 $B$

• 字符串不为"空串"
• 字符格式满足正则规则：$[\text{A}-\text{Z}]$
• 字符串长度 $<10000$

输出描述

原点到终点的最短距离

样例1

输入

ABC ABC

输出

3

样例2

输入

ABCABBA CBABAC

输出

9