• [1632] 01Package

  • 时间限制: 10000 ms 内存限制: 65535 K
  • 问题描述
  • Now I give you n(n <= 40) sugars, each sugar has some value and volum, you also have a package which Volum is V(1 <= V <= 1000000000), Now do you know how to choose these sugars that the sum of value is maximum(the sum of volum <= V)

  • 输入
  • Input starts with an integer T(T <= 10) denoting the number of testcase.
    For each test case, first line contains n and V.
    then n lines following, each line contains the volum and value of ith sugar.
  • 输出
  • For each test case, print the maximum value which you can get.
  • 样例输入
  • 1
    4 10
    3 4
    2 5
    4 5
    5 6
  • 样例输出
  • 15
  • 提示
  • 来源
  • Alex@NBUT
  • 操作

显示春菜