Shortest Common Supersequence

Given two strings \(s_1\) and \(s_2\), find the length of the shortest string that has both \(s_1\) and \(s_2\) as subsequences. A subsequence of a string is formed by deleting zero or more characters without changing the order of the remaining characters.

The problem can be approached using dynamic programming. Define \(dp[i][j]\) as the length of the shortest common supersequence of the first \(i\) characters of \(s_1\) and the first \(j\) characters of \(s_2\). The recurrence relation is given by:

\(dp[i][j] = \begin{cases} j, & i = 0 \\ i, & j = 0 \\ 1 + dp[i-1][j-1], & s_1[i-1] = s_2[j-1] \\ 1 + \min(dp[i-1][j], dp[i][j-1]), & \text{otherwise} \end{cases}\)

Your task is to calculate \(dp[m][n]\) where \(m\) and \(n\) are the lengths of \(s_1\) and \(s_2\), respectively.

Input is provided via standard input and output should be written to standard output.

inputFormat

The input consists of two lines. The first line contains the string \(s_1\) and the second line contains the string \(s_2\). Either string may be empty.

outputFormat

Output a single integer which is the length of the shortest common supersequence of \(s_1\) and \(s_2\).

## sample

AGGTAB
GXTXAYB

9

</p>