快递物流

题目描述

你是一家物流公司的调度员，现在有一辆货运车，其最大容量为V。目前有n件待装车的货物，每件货物都有一个体积v~i~和一个重量m~i~。你的任务是选择一部分货物装入货运车，使得货运车的总容量不超过其最大值V，并且装入货物的总重量最大。

输入格式

第一行包含两个正整数n和V，分别表示货物的数量和货运车的最大容量。（n≤3500，V≤12800） 接下来n行，每行包含两个正整数v~i~和m~i~，分别表示第i件货物的体积和重量。（v~i~，m~i~≤1000）

输出格式

输出一个正整数，表示能装载的最大重量。

5 10  
1 1
5 4  
2 3  
5 5  
6 7

11

提示

（暂无提示）

来源

童程童美