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.