Merging String

問題文

ロボてりーは文字列 $S,T,X$ を持っています。 $X$ は最初、空文字列です。
ロボてりーは $S,T$ がともに空文字列になるまで、以下の操作を上から順に行うことを繰返します。

• $S,T$ のうち、空文字列でないものを選ぶ。(両方空文字列でない場合はどちらを選んでも良い。)
• 選んだ文字列の先頭の要素を削除する。
• 削除された要素を $c$ として、 $X$ の末尾に $c$ を加える。

操作の繰返しを終えた後の $X$ のスコアを、以下の条件を満たす $X$ の連続部分文字列の長さの最大値とします。

条件: 文字列全体が広義単調増加である。

ただし、文字列全体が広義単調増加とは、文字列内の任意の $2$ 要素 $x,y$ について、 $y$ が $x$ よりも右にあるならばアルファベット順で $x \leq y$ が成り立つことをさします。例えば、 "aaa" や "cxyz" は広義単調増加ですが、 "ea" は広義単調増加ではありません。

ロボてりーは忙しいので、代わりに $X$ のスコアとしてあり得るものの最大値を求めてあげてください。

制約

• $1\leq |S|,|T| \leq 1500$
• $S,T$ は英小文字からなる

入力

入力は以下の形式で標準入力から与えられます。

出力

答えを出力してください。

入力例1

abc
arc

出力例1

5

最終的な $X$ としてあり得る文字列として、例えば "aabcrc" がありますが、この文字列のスコアは $5$ であり、この入力においての最適解です。 　
　

入力例2

x
a

出力例2

2

$X =$ "xa" とするとスコアは $1$ ですが、$X =$ "ax" とするとスコアは $2$ になります。 　
　

入力例3

edcba
zyx

出力例3

2

入力例4

hibiki
chan

出力例4

5