class Solution {
public:
    int coinChange(vector<int>& coins, int amount) {
        int n=coins.size();
        sort(coins.begin(), coins.end());
        vector<vector<int> >dp(n, vector<int>(amount+1));
        for(int i=0; i<n; i++){
            dp[i][0]=0;
        }
        for(int j=1; j<=amount; j++){
            if(j%coins[0]==0){
                dp[0][j]=j/coins[0];
            }
            else{
                dp[0][j]=-1;
            }
        }
        for(int i=1; i<n; i++){
            for(int j=1; j<=amount; j++){
                if(coins[i]<=amount){
                    if(j%coins[i]==0){
                        dp[i][j]=j/coins[i];
                    }
                    else{
                        if(dp[i-1][j]==-1  && dp[i-1][j%coins[i]]==-1){
                            dp[i][j]=-1;
                        }
                        else if(dp[i-1][j]!=-1  && dp[i-1][j%coins[i]]==-1){
                            dp[i][j]=dp[i-1][j];
                        }
                        else if(dp[i-1][j]==-1  && dp[i-1][j%coins[i]]!=-1){
                            dp[i][j]=dp[i-1][j%coins[i]] + j/coins[i];
                        }
                        else{
                            dp[i][j]=min( dp[i-1][j%coins[i]] + j/coins[i], dp[i-1][j]);

                        }
                    }
                }
                else{
                    dp[i][j]=dp[i-1][j];
                }
            }
        }
        return dp[n-1][amount];
    }
};