1050: 机甲战士

潘多拉星球上的基地指挥官准备派遣一名机甲战士外出执行任务，为了完成任务，机甲战士需要随身携带足够的生存装备。生存装备里存储着氧气和燃料，且每个装备有一定的重量。机甲战士完成任务所需要携带的氧气和燃料都有最低限量，绝对不能少于这个最低限量，一次任务可以携带多个生存装备备用。当给出最低氧气限量值M(1SMS30)和最低燃料限量值N(1SNS80)，生存装备的数量K(1≤K≤1000)及每个生存装备中氧气值a(1≤a≤30)、燃料值b(1Sb≤80)及装备重量c(1≤c≤100)，请计算出机甲战士要完成任务所需要携带的生存装备的总重量最低是多少，并输出这个最低值。 例如: M=6，N=40，K=5，5个生存装备中的氧气值、燃料值及装备重量分别如下:

可以满足要求的携带方法有:
2号和4号装备的组合(总重量为120);

2号和5号装备的组合(总重量为130);

3号和4号装备的组合(总重量为130);
。。。。。
其中，生存装备的总重量最低为120。

6 40
5
5 5 30
7 15 40
4 20 50
3 25 80
2 30 90

120