You have n packages that you are trying to place in boxes, one package in each box. There are m suppliers that each produce boxes of different sizes (with infinite supply). A package can be placed in a box if the size of the package is less than or equal to the size of the box.

The package sizes are given as an integer array packages, where packages[i] is the size of the ith package. The suppliers are given as a 2D integer array boxes, where boxes[j] is an array of box sizes that the jth supplier produces.

You want to choose a single supplier and use boxes from them such that the total wasted space is minimized. For each package in a box, we define the space wasted to be size of the box - size of the package. The total wasted space is the sum of the space wasted in all the boxes.


	For example, if you have to fit packages with sizes [2,3,5] and the supplier offers boxes of sizes [4,8], you can fit the packages of size-2 and size-3 into two boxes of size-4 and the package with size-5 into a box of size-8. This would result in a waste of (4-2) + (4-3) + (8-5) = 6.


Return the minimum total wasted space by choosing the box supplier optimally, or -1 if it is impossible to fit all the packages inside boxes. Since the answer may be large, return it modulo 109 + 7.

&nbsp;
Example 1:

Input: packages = [2,3,5], boxes = [[4,8],[2,8]]
Output: 6
Explanation: It is optimal to choose the first supplier, using two size-4 boxes and one size-8 box.
The total waste is (4-2) + (4-3) + (8-5) = 6.


Example 2:

Input: packages = [2,3,5], boxes = [[1,4],[2,3],[3,4]]
Output: -1
Explanation: There is no box that the package of size 5 can fit in.


Example 3:

Input: packages = [3,5,8,10,11,12], boxes = [[12],[11,9],[10,5,14]]
Output: 9
Explanation: It is optimal to choose the third supplier, using two size-5 boxes, two size-10 boxes, and two size-14 boxes.
The total waste is (5-3) + (5-5) + (10-8) + (10-10) + (14-11) + (14-12) = 9.


&nbsp;
Constraints:


	n == packages.length
	m == boxes.length
	1 &lt;= n &lt;= 105
	1 &lt;= m &lt;= 105
	1 &lt;= packages[i] &lt;= 105
	1 &lt;= boxes[j].length &lt;= 105
	1 &lt;= boxes[j][k] &lt;= 105
	sum(boxes[j].length) &lt;= 105
	The elements in boxes[j] are distinct.


class Solution:
    def minWastedSpace(self, packages: List[int], boxes: List[List[int]]) -> int:
        # prefix sum to save time
        acc = [0] + [*accumulate(packages)]
        packages.sort()

        ans = float('inf')
        for box in boxes:
            tmp = 0
            # deal with smallest box first
            box.sort()

            # record number of packages already dealt with
            start = 0

            for b in box:
                loc = bisect.bisect(packages, b)
                if loc == 0: continue
                tmp += b * (loc - start) - (acc[loc] - acc[start])

                # all are packaged
                if loc == len(packages):
                    ans = min(ans, tmp)
                    break

                start = loc

        return ans % (10 **9+7) if ans != float('inf') else -1
class Solution {
    public int minWastedSpace(int[] packages, int[][] boxes) {
        Arrays.sort(packages);
        int n = packages.length, k = -1;
        long sum = 0, ans = Long.MAX_VALUE;
        int[] pos = new int[100001];
        for (int i = 0; i < 100001; i++){ // precompute jump position.
            while(k < n - 1 && packages[k+1] == i){
                sum += packages[++k];
            }
            pos[i] = k;
        }
        for (int[] b : boxes){
            Arrays.sort(b);
            long cost = -sum;
            k=-1;
            for (int i = 0; i < b.length; i++){
                if (pos[b[i]] >= 0){
                    int cnt = pos[b[i]]-k;
                    cost += 1L * cnt * b[i];
                    k=pos[b[i]];
                }
            }
            ans = k == n-1? Math.min(cost, ans) : ans;
        }

        return ans == Long.MAX_VALUE? -1 : (int)(ans % (int)(1e9+7));
    }
}
class Solution {
public:
    #define MOD 1000000007
    #define ll long long
    int minWastedSpace(vector<int>& packages, vector<vector<int>>& boxes) {
        
        int n = packages.size();
        int m = boxes.size();
        sort(packages.begin(), packages.end());
        vector<ll> pack(n + 1);
        pack[0] = 0;
        for(int i = 0;i<n; i++){
            pack[i + 1] = packages[i];
            pack[i + 1] += pack[i];
        }
        ll ans = 1e18;
        bool mf = false;
        for(int i = 0; i<m; i++){
            vector<int> opt = boxes[i];
            sort(opt.begin(), opt.end());
            int back = 0;
            ll temp = 0;
            bool flag = false;
            ll bag ;
            for(int j = 0; j<(int)opt.size(); j++){
                
                bag = opt[j];
                auto it = upper_bound(packages.begin(), packages.end(), bag);
                auto it1 = it;
                int idx ;
                if(it != packages.begin()){
                    it--;
                    idx = it - packages.begin();
                    ll num_packs = idx + 1 - back;
                    
                    ll pack_sum = pack[idx + 1] - pack[back];
                    back = idx + 1;
                    temp += (num_packs*bag - pack_sum);
                }
                if(it1 == packages.end()){
                    flag = true;
                    break;
                }  
            }
            if(flag){
                ans = min(ans, temp);
                mf = true;
            }
                 
        }
        if(!mf) return -1;
        
        if(ans == 1e18) return -1;
        ans = ans % MOD;
        return ans;
    }
};
/**
 * @param {number[]} packages
 * @param {number[][]} boxes
 * @return {number}
 */
var minWastedSpace = function(packages, boxes) {
    let count=0,b,minWastage,totalPackagesSize=0n,minBoxesAreaForAnySupplier=BigInt(Number.MAX_SAFE_INTEGER),boxesArea=0n,p,coverdPackagesIndex,totalBoxesAreaForSupplier;
    packages.sort(function(a,b){return a-b});
    for(let i=0;i<packages.length;i++){
        totalPackagesSize+=BigInt(packages[i]);
    }

    for(let i=0;i<boxes.length;i++){
        boxes[i].sort(function(a,b){return a-b});
        p=0;
        totalBoxesAreaForSupplier=0n;
        if(boxes[i][boxes[i].length-1]<packages[packages.length-1]){//This supplier is not big enough box for the largest package, hence this supplier can't be used.
            continue;
        }
        for(let b=0;b<boxes[i].length;b++){
            coverdPackagesIndex = binaryLowerBound(packages,p,packages.length-1,boxes[i][b]);
            if(coverdPackagesIndex!==-1){
                totalBoxesAreaForSupplier+=BigInt(boxes[i][b])*BigInt(coverdPackagesIndex-p+1);
                p=coverdPackagesIndex+1;
                if(p===packages.length){
                    break;
                }
            }
        }
        if(p===packages.length){//Check if the current supplier was able to pack all the packages.
            if(totalBoxesAreaForSupplier<minBoxesAreaForAnySupplier){
                minBoxesAreaForAnySupplier = totalBoxesAreaForSupplier;
            }
        }
    }
    if(minBoxesAreaForAnySupplier!==BigInt(Number.MAX_SAFE_INTEGER)){
        return (minBoxesAreaForAnySupplier-totalPackagesSize)%1000000007n;
    }else{
        return -1;
    }

    function binaryLowerBound(arr,left,right,key){
        let mid,ans=-1;
        while(left<=right){
            mid = left + Math.floor((right-left)/2);
            if(arr[mid]<=key){
                ans=mid;
                left=mid+1;
            }else{
                right=mid-1;
            }
        }
        return ans;
    }
};
Minimum Space Wasted From Packaging