返回信息流阿里内推编程测试，是一个最优化组合的问题，没有头绪，求大神。
**题目描述：**
某玩具店内有编号为1-N的卡片多张，且有玩具M种（第i种的价格为Pi）。每种玩具的包装盒内，有编号固定且连续的卡片（Xi至Yi, 1<=Xi<=Yi<=N）各一张。为了促销开展“集卡”活动。活动内容为集齐N种卡片，且对每种卡片有数量要求（规定编号为i的卡片需要Ni张），即可换得优惠券。请问客户至少花多少钱买这些玩具可以得到一张优惠券。（假设M和N均不大于100）
**输入：**
第一行有两个整数N, M，表示卡片的最大编号和玩具的种类。接下来一行中包含N个非负整数，表示活动需要集齐每种卡片的张数。接下来的M行中每行包含三个整数X, Y, P分别表示这种玩具中卡片编号的起始号、终止号和价格。假定每种玩具都是无限多的。
**输出：**
仅包含一个整数，表示买玩具得到优惠券最少花的费用。
**输入范例：**
4 2
1 3 2 2
1 2 2
2 4 5
**输出范例：**
12
（即买2个5元的，1个2元的）
这是一条镜像帖。来源：北邮人论坛 / acm-icpc / #95647同步于 2018/4/17
该镜像源已超过 30 天没有更新，可能在源站已被删除。
ACM_ICPC机器人发帖
阿里编程测验算法，组合优化最小
qcomedy
2018/4/17镜像同步3 回复
订阅后，新回复会通过你的通知中心匿名送达。
3 条回复
帮顶，求大神解答
我想了一个超级笨的方法，也不知道可不可行。。**对玩具进行排序，按照玩具内有用的卡和价格的比例进行排序**
比如例子中第一个玩具是2元，获得2张有用的卡，比例为1元1张；第二个玩具是5元，获得三张有用的卡，比例为1.6元一张；那就优先选择买第一个玩具，一直到该玩具的价值比发生变化。
比如买了一个玩具1后，待集其卡片数组变为 0 2 2 2。
此时第一个玩具是2元只能获得1张有用的卡（因为1已经集齐了）第二个玩具价值比还是1.6；所以选择优先买第二个玩具，以此类推。
m,n都不超过100，如果思路可行的话应该不会超时吧，求大神指教[ema23]
【 在 a2013211232 的大作中提到: 】
: 帮顶，求大神解答
: 我想了一个超级笨的方法，也不知道可不可行。。**对玩具进行排序，按照玩具内有用的卡和价格的比例进行排序**
: 比如例子中第一个玩具是2元，获得2张有用的卡，比例为1元1张；第二个玩具是5元，获得三张有用的卡，比例为1.6元一张；那就优先选择买第一个玩具，一直到该玩具的价值比发生变化。
: ...................
行吧，我已经发现我错了，还是没解决我最初想避免的那个问题（有不得不买的玩具然后玩具内附加着一些其它卡片的情况），如果是下面这组数据，答案应该是100 + 99，而之前那种方法会是200。。。
2 2
100 1
1 1 1
1 2 100
所以转变思路？从那些不得不买的玩具入手，比如总共只有10个玩具包含第i张卡片，先用我上面那个方法从这10个玩具里面选出来最优的那个，然后再依次类推？我已经迷了