Shortest Common Supersequence Length

Given two strings (s_1) and (s_2), your task is to compute the length of the shortest string that contains both (s_1) and (s_2) as subsequences. In other words, find the length of the shortest common supersequence (SCS). The problem can be formulated using dynamic programming. Let (dp[i][j]) denote the length of the SCS for the first (i) characters of (s_1) and the first (j) characters of (s_2). The recurrence can be written as: [ \begin{cases} dp[0][j] = j, & \text{for } j \ge 0,\ dp[i][0] = i, & \text{for } i \ge 0,\ dp[i][j] = 1 + dp[i-1][j-1], & \text{if } s_1[i-1] = s_2[j-1],\ dp[i][j] = 1 + \min(dp[i-1][j], dp[i][j-1]), & \text{if } s_1[i-1] \neq s_2[j-1]. \end{cases} ] Your program will read two strings from the standard input and output the length of their shortest common supersequence.

inputFormat

The input consists of two lines. The first line contains the string (s_1) and the second line contains the string (s_2). Both strings may consist of lowercase letters and can be empty.

outputFormat

Output a single integer representing the length of the shortest common supersequence of the two strings.## sample

abc
bcd

4