YZOJ P3216 行商
时间限制：1000MS 内存限制：262144KB
难度：\(4.0\)
-
题目描述
有 \(n\) 个货物，每个货物都有各自的重量 \(w_i\) 和价值 \(c_i\)，但是载重量仅为 \(m\) 。
挑选出一些货物，总重量不超过 \(m\)，使价值之和最大。
-
输入格式
第一行，两个整数 \(n\)，\(m\)；
接下来 \(n\) 行，每行两个整数 \(w_i\)，\(c_i\) 。
-
输出格式
一个整数 \(ans\) 。
-
样例输入
|
1 2 3 4 5 |
4 3 3 10 2 7 2 8 1 1 |
-
样例输出
|
1 |
10 |
-
数据规模与约定
\(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\) 。