409516: GYM103604 K Split

You are given an array $$$A$$$ of $$$N$$$ integers $$$A_1$$$, $$$A_2$$$, …, $$$A_N$$$, and an array $$$B$$$ of $$$K$$$ integers $$$B_1$$$, $$$B_2$$$, …, $$$B_K$$$.

You are asked to split the array $$$A$$$ into $$$K$$$ non-empty subarrays (consecutive positions within the array). The cost of a split is equal to $$$\sum_{i=1}^{K} max_i^{B_i} - min_i^{B_i}$$$, where $$$max_i$$$ denotes the maximum in the $$$i^{\text{th}}$$$ subarray, and $$$min_i$$$ denotes the minimum in the $$$i^{\text{th}}$$$ subarray.

Calculate the maximum cost you can obtain by splitting the array $$$A$$$ into $$$K$$$ non-empty subarrays.

The first line contains two integers: $$$N$$$ $$$(1 \leq N \leq 5000)$$$ and $$$K$$$ $$$(1 \leq K \leq N)$$$.

The second line contains $$$N$$$ integers: $$$A_1$$$, $$$A_2$$$, …, $$$A_N$$$ $$$(1 \leq A_i \leq 10^5)$$$.

The third line contains $$$K$$$ integers: $$$B_1$$$, $$$B_2$$$, …, $$$B_K$$$ $$$(1 \leq B_i \leq 3)$$$.

On a single line, print the maximum cost you can obtain by splitting the array $$$A$$$ into $$$K$$$ non-empty subarrays.

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

1079