<p>You are assigned to put some amount of boxes onto <strong>one truck</strong>. You are given a 2D array <code>boxTypes</code>, where <code>boxTypes[i] = [numberOfBoxes<sub>i</sub>, numberOfUnitsPerBox<sub>i</sub>]</code>:</p>

<ul>
	<li><code>numberOfBoxes<sub>i</sub></code> is the number of boxes of type <code>i</code>.</li>
	<li><code>numberOfUnitsPerBox<sub>i</sub></code><sub> </sub>is the number of units in each box of the type <code>i</code>.</li>
</ul>

<p>You are also given an integer <code>truckSize</code>, which is the <strong>maximum</strong> number of <strong>boxes</strong> that can be put on the truck. You can choose any boxes to put on the truck as long as the number&nbsp;of boxes does not exceed <code>truckSize</code>.</p>

<p>Return <em>the <strong>maximum</strong> total number of <strong>units</strong> that can be put on the truck.</em></p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> boxTypes = [[1,3],[2,2],[3,1]], truckSize = 4
<strong>Output:</strong> 8
<strong>Explanation:</strong> There are:
- 1 box of the first type that contains 3 units.
- 2 boxes of the second type that contain 2 units each.
- 3 boxes of the third type that contain 1 unit each.
You can take all the boxes of the first and second types, and one box of the third type.
The total number of units will be = (1 * 3) + (2 * 2) + (1 * 1) = 8.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> boxTypes = [[5,10],[2,5],[4,7],[3,9]], truckSize = 10
<strong>Output:</strong> 91
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= boxTypes.length &lt;= 1000</code></li>
	<li><code>1 &lt;= numberOfBoxes<sub>i</sub>, numberOfUnitsPerBox<sub>i</sub> &lt;= 1000</code></li>
	<li><code>1 &lt;= truckSize &lt;= 10<sup>6</sup></code></li>
</ul>

class Solution {
public:
    //THE COMMENTED APPORACH IS CORRECT BUT IS TOO HUGE TO USE IN THIS 
    //QUESTION

    // int solve(vector<vector<int>>& arr, int target, int i, vector<vector<int>> &dp){
    //     //base case
    //     if(target==0){
    //         return 0;
    //     }
    //     if(i>=arr.size()){
    //         return 0;
    //     }
    //     if(dp[i][target]!=-1){
    //         return dp[i][target];
    //     }

    //     int a=solve(arr,target,i+1,dp);
    //     int b=0;

    //     for(int j=1;j<=arr[i][0];j++){
    //         if(j<=target){
    //             int maxi=(j*arr[i][1])+solve(arr,target-j,i+1,dp);
    //             b=max(b,maxi);
    //         }
    //     }
    //     return dp[i][target] = max(a,b);
    // }

    static bool comp(pair<int,int>a , pair<int,int>b){
        return a.second>b.second;
    }

    int maximumUnits(vector<vector<int>>& boxTypes, int truckSize) {

        vector<pair<int,int>>mp;

        for(int i=0;i<boxTypes.size();i++){
            mp.push_back({boxTypes[i][0],boxTypes[i][1]});
        }

        sort(mp.begin(),mp.end(),comp);
        int ans=0;
        for(auto x:mp){
            if(truckSize==0){
                break;
            }
            if(truckSize>=x.first){
                cout<<"1"<<" "<<truckSize<<endl;
                ans+=(x.first*x.second);
                truckSize-=x.first;
            }
            else{
                cout<<"2"<<" "<<truckSize<<endl;
                ans+=(truckSize*x.second);
                truckSize=0;
            }
        }
        return ans;

        // vector<vector<int>>dp(boxTypes.size(),vector<int>(truckSize+1,-1));
        // return solve(boxTypes, truckSize, 0, dp);
    }
};
20300