🌳 题目描述：

题目内容

M 种商品，N 元本金，每种商品原件 X 元，一件折扣价 Y 元，两件折扣价 Z 元（X >= Y >=Z），求最大的折扣金额

输入描述

第一行输入两个整数 M，N：

接下去 K 行输入三个数 X, Y, Z

输出描述

输出最大的折扣金额

样例:

输入
3 50
10 8 6 
20 15 12
30 25 18

输出
32

解释：

可以买两件原价 30 元的一共花费 18 * 2 = 36 元，共折扣 (30 - 18) * 2 = 24 元，剩下 14 元可以买两件原价 10 元的商品，花费 6 * 2 = 12 元，共折扣 (10 - 6) * 2 = 8元，剩下一元无法购买商品，最大的折扣金额为 24 + 8 = 32 元

🕵🏽 面试评估：

这道题为经典动态规划背包问题的变种，属于难题

🧗难度系数：

⭐️ ⭐️ ⭐️ ⭐️ ⭐️

提示

思路分析，题解，代码，复杂度分析仅对算法/后端训练营用户开放