LCS 9

Time limit2sMemory limit1024 MB

Summary

Given strings A and B, sum the LCS lengths over every prefix of A paired with every substring of B.

Level: Hard8 of 10
Topics: Dynamic programming, String
Solved: No attempts yet

Problem

The longest common subsequence (LCS) problem asks for the longest sequence that is a subsequence of both given sequences. For example, the LCS of ACAYKP and CAPCAK is ACAK. A prefix of a string is a nonempty string made by removing zero or more characters from the end of the string. A string of length $N$ has $N$ prefixes. A substring of a string is a nonempty string made by removing zero or more characters from the front and the back of the string. A string of length $N$ has $N(N+1)/2$ substrings. Given two strings, take every pair of a prefix of the first string and a substring of the second string, find the LCS length of each pair, and output the sum of all these lengths.

Input

The first and second lines each contain a string. Each string consists only of uppercase English letters and has at most 7000 characters.

Output

Print the answer to the problem on the first line.

Examples2

Example 1
Input
```
ACAYKP
CAPCAK
```
Expected output
```
197
```

Example 2

Input

WEDONTNEEDNOEDUCATION
WEDONTNEEDNOTHOUGHTCONTROL

Expected output