背包问题扩展——解公司外包成本问题

小米所在的公司需要至少W个其他公司提供的外包人员，现在有N家公司向小米的公司提供了可选方案，其中

Pi代表可提供外包人员单位数，如5人为一个单位数，若选用该公司方案，则必须采用整单位数的人数，如5人为一个单位数，则X公司只能采用n*5个人数（n=0,1,2,….)。Ci代表为Pi单位数员工提供的总工资，单位是万元

输入格式：

N W

Pi C i

请问，采取什么样的方案可以满足公司花最少的开销招到至少W个外包人员，求出最少的开销金额。

例如公司需要至少15个外包员工，A公司的价格方案是 2万元/每三人，B公司的价格方案是 3万元/每五人。

-Knapsack problem expansion- the solution company outsourcing costs millet where at least W other companies to provide outsourced staff, there is now the N company the millet company offers an optional program, where Pi represents the outsourcers number of units, 5 people a number of units, if the choice of the company' s program, it must be a whole number of units the number of people, such as 5 were a number of units, the X only n* 5 individuals (n = 0,1,2, ... ). Ci representative the Pi unit of the number of employees the total wages, the unit is the yuan input format: NW Pi C i ask to take what kind of programs to meet the company spend the least cost to hire at least W outsource staff obtained a minimum of overhead amount. For example, the company needs at least 15 outsourcing employees A company' s price of the program is 20,000 yuan/every three B Company of the price of the program is 30,000 yuan/every five people.