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$ 。

 

 

 …