409603: GYM103643 F Changing Numbers
Description
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.
InputThe 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$$$.
OutputOutput a single integer, the minimum cost needed to modify the list to satisfy the conditions.
ExampleInput5 3 2 2 1 2 2 2 2 1Output
2Note
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