Optimizing Study Plan

You are given a summer vacation lasting n days. On day \(i\), you have an energy index of \(a[i]\). You want to review m subjects in sequence (i.e. subject 1, 2, \(\dots\), m). The \(i\)th subject has an importance value of \(b[i]\). For each subject, you must choose a contiguous, non‐empty segment of consecutive days to review, and you cannot skip any day in between.

If you review subject \(i\) in days \(l\) to \(r\) (inclusive), the gain from that subject is:

[ b[i] \times \sum_{k=l}^{r} a[k] ]

Your total gain is the sum of the gains of all \(m\) subjects. In other words, if you partition the sequence of days \(1,2,\dots,n\) into \(m\) consecutive segments with sums \(s[1], s[2], \dots, s[m]\), your total gain is:

[ \sum_{i=1}^{m} b[i] \times s[i] ]

Determine a review plan (i.e. a partition) that maximizes the total gain.

Example 1: Let \(a = [-3, 6, -1, -8, 7, -6]\) and \(b = [-3, 2]\). The optimal strategy is to review subject 1 on days 1 to 4, yielding a gain of \(-3 \times (-3+6-1-8)=18\); and subject 2 on days 5 to 6, yielding a gain of \(2 \times (7-6)=2\). The total gain is \(18+2=20\).

Example 2: Let \(a = [6, 3, 5, 10, 5]\) and \(b = [-8, -5, -5]\). The optimal partition is \([1], [2,3,4], [5]\) and the total gain is \(-8 \times 6 -5 \times (3+5+10) -5 \times 5 = -163\).

inputFormat

The first line contains two integers \(n\) and \(m\): the number of days and the number of subjects.

The second line contains \(n\) space-separated integers \(a[1], a[2], \dots, a[n]\) representing the energy indices for each day.

The third line contains \(m\) space-separated integers \(b[1], b[2], \dots, b[m]\) representing the importance of each subject, in the review order.

outputFormat

Output a single integer: the maximum total gain that can be achieved by optimally partitioning the days among the subjects.

sample

6 2
-3 6 -1 -8 7 -6
-3 2

20