ACM一道题 求大神给出思路或者代码 谢谢~~~~

Question

Problem Description
CZJ的舍友请CZJ吃饭，作为舍友CZJ是不会放过吃穷舍友的机会，但自己身体又不好，不能吃太多也不能吃太少。假设每样食物都有一个饱腹度和价值，请你帮他算下刚好吃饱的情况下最多可以吃他舍友多少钱。
Input
第一行是一个T，代表数据的组数T（T≤100001）。每组两个整数p，y（1≤p≤1000，1≤y≤100），分别表示食物的数量和CZJ的饱腹度。
然后p个数Qpi表示第pi个食物的价值，之后p个数Mpi表示吃第pi个食物得到的饱腹度。（1≤Qpi≤10000，1≤Mpi≤1000）。
Output
对于每一个样例输出CZJ能吃下的最大价值。
Sample Input

1
5 100
11 6 7 5 6
40 50 60 20 30

Sample Output

18

Author
SCNU20102200088

Answer 1

看完题目的第一想法，就是背包问题。T组则是解决T个背包问题。
实际上每组的背包问题，还是很好解决的。
感觉问题重点还是在于空间的优化上，以及大数据的计算优化上。
还有不知道你是不是贴错题目了，1≤y≤100，然而1≤Mpi≤1000?
如果真这样的话，那不表示Mpi大于100，直接排除这个食物？