Problem H: Harvesting Crops

One of the objectives of a popular Farming game is to grow crops and turn them into profits. The player can choose a number of different crops to grow for different amounts of profit, though different crops also take different amounts of time to grow. For example, it may take 12 hours for apples to grow on a tree for a profit of $200, but it only takes 2 hours to grow grapes for a profit of $40. Clearly, growing grapes 6 times in 12 hours is more profitable. The player must be in front of the computer to select the crop to grow after the previous one has finished. However, the player will still receive the profit if the crop finishes while the player is away. The next crop can be grown when the player is in front of the computer again. In this problem, each player can grow at most one crop at a time.

You will be given the growing times and the profits of N crops (N ≤ 1000). You will also be given a list of times at which you will be in front of the computer over a period of 2 days. All times will be given in minutes from midnight, between 1 and 2880. You may assume that no crops are growing at minute 1. Any crops that have not finished growing at the end of 2 days cannot be turned into profit. If a crop is started at minute T and takes G minutes to grow, then the crop finishes growing and is turned into profit at the end of minute T+G-1. The next crop can be started at or after minute T+G.

At every minute that you are in front of the computer, you will check to see if it is possible to start a new crop. If so, you may choose to grow any of the given crops.

Your program will report the maximum profit that can be obtained at the end of 2 days.

Input Format

The first line of input contains a single integer indicating the number of cases (at most 100). The first line of each case contains two positive integers N and M separated by a space (N ≤ 1000, M ≤ 100). N specifies the number of different crops available, and M is the number of time intervals in which the player is in front of the computer. Each of the next N lines describes a crop, and consists of two positive integers G and P separated by a space (G ≤ 2880, P ≤ 1000). G is the number of minutes required to grow the crop, and P is the profit for that crop. This is followed by M lines each containing two integers S and E indicating that the player is in front the computer from minute S to minute E inclusive (1 ≤ S ≤ E ≤ 2880). No intervals overlap.

Output Format

For each case, print on a line the maximum profit that can be made at the end of 2 days.

Sample Input

1
2 1
720 200
120 40
1 2880

Sample Output

960

Howard Cheng
ACPC 2013