Knapsack 4

View as PDF

Submit solution

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 n mathies and m engineers. Participant i has strength w_i and meme value v_i.

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, T (1 \le T \le 30). T test cases follow.

For each test case, the first line contains two integers n,m (1 \le n,m \le 1\,000), representing the number of mathies and engineers respectively.

Then (n + m) lines follow, describing the students. The ith line contains two integers w_i, v_i (1 \le w_i \le 1\,000, -10^9 \le v_i \le 10^9), representing the strength and the meme value by the ith participant. The first n are mathies, while the other m are engineers. The sum of (n + m) in all test cases doesn't exceed 10^4.

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

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


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


There are no comments at the moment.