409603: GYM103643 F Changing Numbers

Allie is given a list of $$$n$$$ numbers, $$$a_1, a_2, \ldots, a_n$$$. She is given $$$m$$$ conditions, $$$b_1, b_2, \ldots, b_m$$$, denoting that the list should be modified to contain $$$b_i$$$ occurrences of the number $$$i$$$. Allie can add or subtract $$$1$$$ from an element in the list, both operations having $$$1$$$ cost. Help her find the minimum cost needed to modify the list to satisfy the conditions.

The first line contains two integers, $$$n$$$ ($$$1 \leq n \leq 10^5$$$), and $$$m$$$ ($$$1 \leq m \leq 10^5$$$).

The second line contains $$$n$$$ integers $$$a_1, a_2, \ldots, a_n$$$ ($$$1 \leq a_i \leq 10^6$$$).

The third line contains $$$m$$$ integers $$$b_1, b_2, \ldots, b_m$$$ ($$$0 \leq b_i \leq n$$$).

It is guaranteed that $$$\sum b_i = n$$$.

Output a single integer, the minimum cost needed to modify the list to satisfy the conditions.

5 3
2 2 1 2 2
2 2 1

2

One solution is to subtract $$$1$$$ from the $$$1$$$st element and add $$$1$$$ to the $$$2$$$nd element, with a total of $$$2$$$ cost. The resulting sequence is $$$1$$$ $$$3$$$ $$$1$$$ $$$2$$$ $$$2$$$, which contains $$$2$$$ $$$1$$$'s, $$$2$$$ $$$2$$$'s, and $$$1$$$ $$$3$$$, satisfying all the conditions. There is no way to fulfill the conditions with less cost, so the answer is $$$2$$$.

$$$---------------------------------------------$$$

Problem Idea: Mantlemoose

Problem Preparation: Mantlemoose

Occurrences: Novice 7