Processing math: 100%

YZOJ P3216 行商

YZOJ P3216 行商

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

难度:4.0

  • 题目描述

n 个货物,每个货物都有各自的重量 w_i 和价值 c_i,但是载重量仅为 m

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

  • 输入格式

第一行,两个整数 nm

接下来 n 行,每行两个整数 w_ic_i

  • 输出格式

一个整数 ans

  • 样例输入

  • 样例输出

  • 数据规模与约定

 1 \leq n \leq 10^61 \leq m \leq 4^{31}1 \leq w_i \leq 31 \leq c_i \leq 10^9

 

 

 …