P8239 [AGM 2022 Qualification Round] Split

You have an array $a$ of length $n$. You need to split it into $K$ non-empty subsegments. The final score is $\sum_{i=1}^K mx_i^{b_i}-mn_i^{b_i}$, where $b_i$ is a given constant, $mx_i$ is the maximum value in the $i$-th segment, and $mn_i$ is the minimum value in the $i$-th segment. What is the maximum score you can obtain?

The first line contains two positive integers $n, K$. The next line contains $n$ integers representing $a_i$. The next line contains $K$ integers representing $b_i$.

Output one integer in a single line, representing the answer.

#### Constraints For $100\%$ of the testdata, it is guaranteed that $1 \leq K \leq n \leq 5000$, $1 \leq a_i \leq 10^5$, and $1 \leq b_i \leq 3$. #### Notes Translated from [AGM 2022 Qualification Round K Split](https://judge.agm-contest.com/public/problems/11/text)。 Translated by ChatGPT 5