## Knapsack 4

View as PDF

Points: 20
Time limit: 5.0s
Memory limit: 512M

Problem type

Rope Pulling, also known as Tug of War, is a classic game. After acquiring a very very very large tie under suspicious circumstances, Zhang3 is using it to organize such a game between mathies and engineers.

There are mathies and engineers. Participant has strength and meme value .

To make the game more interesting, Zhang3 wants to choose the teams to have same total strengths, while maximizing the total meme values of all participants.

Output the maximum meme value possible. Note that empty teams are also allowed.

#### Input Specification

The first line of the input gives the number of test cases, . test cases follow.

For each test case, the first line contains two integers , representing the number of mathies and engineers respectively.

Then lines follow, describing the students. The th line contains two integers , representing the strength and the meme value by the th participant. The first are mathies, while the other are engineers. The sum of in all test cases doesn't exceed .

#### Output Specification

For each test case, print a line with an integer, representing the maximum total meme value of two teams with the same total strength values.

#### Sample Input

2
3 4
4 7
3 8
2 2
1 4
5 8
1 3
4 4
1 2
1000 -10000
200 3000
800 5000

#### Sample Output

30
0

Problem Resource: 2020 Multi-University Training Contest 4, Hangzhou Xuejun Contest, Problem C