Preparing NOJ

ELEVATOR

1000ms 65536K

Description:

In the library of NUPT there is an elevator. The elevator can lift no more than W kg.
And you know in NUPT the library is always crowded.
Here are N people want to get into the elevator. Each people have two facts, the weight and IQ.
I want you to find the minimum of the combined IQ of the people outside the elevator when the combined weight of the people in the elevator is no more than W.
For example: when W,n=200,4
        The weight of people are: 65 50 85 55
        The IQ of peole are:     46 18 70 21
65+50+85+55=255>W, so the elevator can lift them all.
We chose to lift the 1st,2nd,3rd people, the sum of weight is 200<=W and the sum of  IQ of people out of the elevator is 21.
So you have to output 21.

Input:

In the first line there is an integer T indicating there T test cases.
In the first of each case, there are two integers W,n.W is the max weight of peole in the elevator, and there are n people.
In the next line there are n integers wi. The ith integer is the ith people’s weight.
In the next line there are n integers vi. The ith integer is the ith people’s IQ.

Output:

For each case you only output one integer. The combined IQ of the people outside the elevator.

Sample Input:

2
0 1
1
1
200 4
65 50 85 55
46 18 70 21

Sample Output:

1
21

Note:

null

本题由旧版NOJ导入,来源:3B

Info

NOJ

Provider NOJ

Code NOJ1996

Tags

Submitted 2

Passed 1

AC Rate 50%

Date 04/20/2019 10:03:10

Related

Nothing Yet