• [J] Smart Cat

  • 时间限制: 1000 ms 内存限制: 65535 K
  • 问题描述
  • Long long ago, there is a smart fat cat, she likes eating fish very much. One day the cat decided to go to fish, she brought a bucket, it can load at most N kg things.After a day's work, the cat caught T fishes, each fish has its own weight and delicious degree. Obviously the cat can not take all of them away. The cat is smart but greedy, so she always picks up the most valuable fish(if she can).


  • 输入
  • Each test case will begin with a integer N(1 <= N <= 125000)and a integer T(1 <= T <= 50). then three lines follow, means weight、value and number, each number ranges from 1 to 100.
  • 输出
  • For each test case,output the sum of delicious degree in the bucket.
  • 样例输入
  • 7 4
    2 4 3 1
    3 2 4 1
    1 1 1 1
    9 4
    1 2 2 1
    1 4 6 4
    10 4 1 3
  • 样例输出
  • 8
    26
  • 提示
  • More details: if two fish have the same "value", take the heavier one.
  • 来源
  • Mr.Cai
  • 操作

显示春菜