Problem Description

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?

Input Format

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 Format

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

10 3
2 6 10 1 5 9 7 2 1 8
3 1 2

1079

Hint

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。

Translated by ChatGPT 5