Two great musicians, Alice and Bob, each composed a sequence of notes. Each note has an intensity (which may be positive or negative), representing how strongly it resonates.
Two great musicians, Alice and Bob, each composed a sequence of notes. Each note has an intensity (which may be positive or negative), representing how strongly it resonates.
When the royal orchestra plays, Alice and Bob may each select some of their notes (keeping their original order) to perform together, forming a duet. However, they must each pick the same number of notes, so that their performances align perfectly.
The harmony value of their duet is calculated as the sum of the products of the paired notes intensities.
Find the maximum possible harmony value that Alice and Bob can achieve, that is, the maximum dot product of two (equally long) subsequences of their compositions.
The first line of input contains \(n\), the length of the original sequence of Alice. The second line contains \(n\) space-separated values \(a_1, a_2, \ldots, a_n\) representing the original sequence of notes of Alice.
The third line of input contains \(m\), the length of the original sequence of Bob. The fourth line contains \(n\) space-separated values \(b_1, b_2, \ldots, b_m\) representing the original sequence of notes of Bob.
The output should be a line with one integer representing the maximum possible harmony, as described.
| Example Input | Example Output |
4 2 1 -2 5 3 3 0 -6 |
18 |
Explanation of example
Take subsequence \(2\) \(-2\) from Alice and subsequence \(3\) \(-6\) from Bob. Their harmony value is \((2 \times 3 + (-2) \times (-6)) = 18\).