有N种物品，每种物品都有两个属性 vi 与 ci，分别表示这种物品的体积和件数。

从这些所给物品中，选出若干件，使其体积之和为S，有多少种方案？求S从1到M的答案。

两种方案不同，当且仅当其中某种物品件数不同。

$n*m<=2.5\times 10^7,1<=n<=5000,1<=m,v_i,c_i<=5\times10^5$