시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
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