Maximize Score by Dividing Array Segments

You are given an array \(a\) of length \(n\) and a sequence of \(K\) integers \(b_1, b_2, \ldots, b_K\). You need to partition the array into \(K\) non-empty contiguous segments. For the \(i\)-th segment, let \(mx_i\) be the maximum element and \(mn_i\) be the minimum element in that segment. The score of the \(i\)-th segment is defined as:

[ \text{score}_i = mx_i^{b_i} - mn_i^{b_i} ]

Your task is to determine the maximum total score, which is given by:

[ \text{Total Score} = \sum_{i=1}^{K}\left(mx_i^{b_i} - mn_i^{b_i}\right) ]

Compute and output the maximum total score you can achieve by partitioning the array appropriately.

inputFormat

The first line contains two integers \(n\) and \(K\) \((1 \leq K \leq n)\) — the length of the array and the number of segments.

The second line contains \(n\) integers \(a_1, a_2, \ldots, a_n\) representing the array.

The third line contains \(K\) integers \(b_1, b_2, \ldots, b_K\) representing the exponents for each segment.

outputFormat

Output a single integer, the maximum total score obtainable by partitioning the array into \(K\) contiguous non-empty segments.

sample

3 2
1 3 2
1 2

5