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 。