快递物流

题目描述

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

输入格式

第一行包含两个正整数 n 和 V，分别表示货物的数量和货运车的最大容量。（n≤3500，V≤12800）

接下来 n 行，每行包含两个正整数 v_i 和 m_i，分别表示第 i 件货物的体积和重量。（v_i，m_i≤1000）

输出格式

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

样例

样例 1

输入

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

输出

11

数据范围

对于 100% 的数据：n≤3500，V≤12800，1≤v_i，m_i≤1000。

知识点与难度

• 知识点：DP(背包问题)
• 来源标签：DP(背包问题)、第二十四讲(Level3)
• 难度：Mid-
• GESP等级：6级
• 本题分值：1550（GESP 6级基准 1350 + Mid- 难度浮动 200）
• 时间限制：1000MS，内存限制：64MB

测试点分布表