/* 美团外卖劵， 满足最低花费的价格
dp[0][...] : 菜品数量为 0，这种情况不正常，用较大数说明不正常
dp[...][0]: 优惠券数量为0， 因此最低消费 0 元

dp[i][j]: 菜品数量为 i 时， coupy 为 j 时的最低花费

当 j < 当前价格， 则最低消费是 Min(dp[i-1][j] , cur_prices) 相同 coupy 菜品数减1后的最低消费
当 j > 当前价格， 则最低消费是 dp[i-1][j] ， dp[i-1][j - cur_price]
*/
const kind = ["5", "20"];
const prices = ["5","5","5", "5", "5"];

const kinds = parseInt(kind[0]);
const coupy = parseInt(kind[1]);

for(let i =0; i < prices.length; i++){
prices[i] = parseInt(prices[i]);
}

const dp = Array(kinds + 1).fill(999);
for(let i = 0; i < dp.length ; i++){
dp[i] = Array(coupy + 1).fill(999);
}

for(let i = 0; i < dp.length; i++){
dp[i][0] = 0;
}

for(let i = 1; i <= kinds; i++){
for(let j = 1; j <= coupy; j++){
if((j - prices[i - 1]) > 0){
dp[i][j] = Math.min(dp[i - 1][j], dp[i - 1][j - prices[i - 1]] + prices[i - 1]);
} else {
dp[i][j] = Math.min(dp[i - 1][j], prices[i - 1]);
}
}
}

console.log(dp[kinds][coupy]);