20790번 - Choose Two Subsequences 다국어

문제

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.

힌트