시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 0 0 0 0.000%

## 문제

Clara has two strings $s$ and $t$. She would like to choose two subsequences $x$ from $s$ and $y$ from $t$ such that:

• $x$ is lexicographically smaller than or equal to $y$.
• The sum of $|x|$ and $|y|$ is maximal, where $|s|$ denotes the length of the string $s$.

Note that:

• Both $x$ and $y$ could be empty string.
• A subsequence is a sequence that can be derived from the given sequence by deleting zero or more elements without changing the order of the remaining elements.
• String $x$ is lexicographically less than string $y$, if either $x$ is a prefix of $y$ (and $x \ne y$), or there exists such $i$ ($1 \le i \le \min(|x|, |y|)$), that $x_i < y_i$, and for any $j$ ($1 \le j < i$) $x_j = y_j$.

## 입력

The input consists of several test cases terminated by end-of-file. For each test case:

The first line contains a string $s$. The second line contains a string $t$.

## 출력

For each test case, output the sum of $|x|$ and $|y|$.

## 제한

• $1 \le |s| \le 2000$
• $1 \le |t| \le 2000$
• The sum of $|s|$ does not exceed $20000$.
• The sum of $|t|$ does not exceed $20000$.
• Both the strings consist only of English lowercase letters.

## 예제 입력 1

aaaa
bbbb
abcd
abca
abcd
abcd


## 예제 출력 1

8
7
8