문제

태경이는 리듬게임 마이마이를 한다. 마이마이에는 슬라이드라는 신기한 기능이 있다. 슬라이드는 센서를 일정한 순서대로 지나간다. 이 센서를 순서대로 눌림으로서 슬라이드의 점수를 얻을 수 있다.

다만 슬라이드는 끝 센서만 누른다면 중간 센서들은 한칸식 건너 띌 수 있다. 예를 들어 슬라이드가 $ABCDEF$를지난다면 $ABCDEF$, $BDEF$, $ACEF$ 등의 방법으로 처리할 수 있다. 악마같은 제작자들은 슬라이드를 가끔 두개를 동시에 처리하게 시킨다. 이때 두 슬라이드가 같은 센서를 지난다면 그 센서는 한번만 누름으로서 두 슬라이드에서 모두 인식시킬 수 있다. 예를 들어 슬라이드 $ABC$와 $AEC$가 있다면 $A$,$C$ 두개의 센서만 입력함으로서 두 슬라이드 모두 처리할 수 있는것이다.

태경이는 굉장히 고난도의 곡을 하는 것을 좋아하고 슬라이드를 제외하고 약 2119개의 음을 더 처리해야 하기에 슬라이드를 처리할때 체력을 최대한 아끼고자 한다. 태경이를 위해서 두개의 슬라이드가 주어질때 인식시켜야 하는 센서의 최소 개수를 구해주자.

입력

첫번째 줄에 두 슬라이드가 각각 지나는 센서의 문자열 $A$,$B$의 각각의 길이 $n$,$m$이 주어진다. ($1≤n,m≤5\,000$)

그 다음 두개의 줄에 문자열 $A$,$B$가 차례대로 주어진다.

출력

두 슬라이드를 둘다 처리하기 위한 최소 센서의 개수를 출력하라.

예제 입력 1

5 5
ABCDE
QBFDE

예제 출력 1

3

예제 입력 2

3 1
ABA
B

예제 출력 2

2