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.