I am stuck in this problem for past few days, need some help. We are given an array with input size(1, 2000) which consists of digits.

We are given a set of pair of digits (N,M) = {(N1,M1), (N2,M2), (N3,M3), (N4,M4)} containing exactly 4 elements.

In pair (N, M), N denotes the digit and M corresponds to the minimum need of the number in the array.

Output is an array that has a minimum count of each element of N. We need to make some changes in original array to get the output such that cost is minimized.

Let C(x, y) be cost of changing number x to number y, then C(x, y) = |x-y|. Our task is to minimize the total cost of changes.

Input Format
First line: Consists of the array
Four lines continue each containing pair (Nx, Mx) where xE{1, 2, 3, 4}

Output Format
Total cost of changes.

Example 1: If an array is {1, 2, 3, 4, 5} and N values of pair (N, M) are 2, 3, 4, 5. Now lets consider that minimum one 2, zero 3, two 4 and zero 5 are needed in array, the input will be like:

1 2 3 4 5
2 1
3 0
4 2
5 0

Output:
1

Explanation
We change 5 to 4 and cost becomes |5-4| and we get Output array {1, 2, 3, 4, 4}

Example 2:

1 1 1 5 3 7 7 7 8 9 6 5 4 1 2
1 1
3 5
5 0
8 2

Explanation
This means that minimum one 1 , five 3's, zero 5's and two 8's should be present in array.

We change 2 to 3, 4 to 3, two 5 to 3. Cost for this change is 6. Then we change 9 to 8 and cost becomes 7. This is the minimal cost and we get magic array {1, 1, 1, 3, 3, 7, 7, 7, 8, 8, 6, 5, 3, 1, 3}

My Approach
My approach to this problem was a greedy approach in which I checked the closest digit to the given digit of N and then changed that digit. This approach wont work every time. Sometime it would be better to use a digit other than the closest digit to find minimum cost as this closest digit can be used by other digit of set N for replacement to obtain a better cost.

Example for which Approach Fail

1 1 2 3 4 4 4 7 9 10
3 4
7 3
9 1
10 1

Explanation:
In this case if we use greedy approach then, for 3 we will change 2 and two 4s to 3 which is wrong as this step will increase total cost.

Minimum cost for this solution is when array changes to 1 3 3 3 3 7 7 7 9 10 ans output becomes 10 which by using greedy-approach comes out to be 12.