Longest Common Interleaved Subsequence

You are given three strings S₁, S₂ and T consisting of lowercase English letters. Your task is to determine the maximum length of a common subsequence that can be obtained by interleaving (i.e. merging while preserving individual order) S₁ and S₂ into a new string M, and then finding a subsequence in common between M and T.

More formally, you must choose an interleaving of S₁ and S₂ (i.e. a string M such that M is a shuffle of S₁ and S₂ with the order of characters in S₁ and S₂ preserved) so that the length of the longest common subsequence (LCS) between M and T is maximized. Output the maximum possible length of this LCS.

Note: The interleaving M is uniquely determined by the order in which you choose characters from S₁ and S₂, and you must use all characters from both S₁ and S₂.

Example 1: For S₁ = "abc", S₂ = "def" and T = "adbecf", one optimal interleaving is "adbecf" which has an LCS with T of length 6.

inputFormat

The input consists of three lines:

• The first line contains the string S₁.
• The second line contains the string S₂.
• The third line contains the string T.

outputFormat

Output a single integer, the maximum length of the longest common subsequence between the interleaved string M (formed by S₁ and S₂) and T.

abc
def
adbecf

6