Preparing NOJ

# Warcraft III

2000ms 65536K

## Description:

John likes playing Warcraft III. Now, he is teaching his girlfriend to play it. In Warcraft III, there are many kinds of units. Every unit costs some gold and lumber. Different units have different attack value.

Now question comes. Given some amount of gold and a list of types of units, how to arrange your units to maximize the attack value of your units. Assume you have infinite lumbers.

## Input:

Line 1 contains an integer T: the number of test cases.

Next T blocks, each starts with two integers: G and U, represents the amount of gold and number of unit type. Next U lines, each contains two integers: attack value of a type of unit and the cost.

## Output:

For each test case, output the maximum total attack value in one line.

## Sample Input:

2100 120 10300 4100 60250 120120 10035 20

## Sample Output:

200605

## Note:

Info

Provider NOJ

Code NOJ1443

Tags

Submitted 1

Passed 1

AC Rate 100%

Date 04/20/2019 10:03:10

Related

Nothing Yet