YZOJ P3216 行商

时间限制：1000MS      内存限制：262144KB

难度：\(4.0\)

• 题目描述

有 \(n\) 个货物，每个货物都有各自的重量 \(w_i\) 和价值 \(c_i\)，但是载重量仅为 \(m\) 。

挑选出一些货物，总重量不超过 \(m\)，使价值之和最大。

• 输入格式

第一行，两个整数 \(n\)，\(m\)；

接下来 \(n\) 行，每行两个整数 \(w_i\)，\(c_i\) 。

• 输出格式

一个整数 \(ans\) 。

• 样例输入

• 样例输出

• 数据规模与约定

 \(1 \leq n \leq 10^6\)，\(1 \leq m \leq 4^{31}\)，\(1 \leq w_i \leq 3\)，\(1 \leq c_i \leq 10^9\) 。

 

 

 …