1761: Treasure Hunter

Raven likes adventure, so he eventually becomes a treasure hunter after numerous tough experiences. For his new role, the first task is to go to a maze and dig out the treasure there. After seeing the map of the maze, Raven finds out that it is an n*m rectangle. When Raven takes a step to any direction, up or down, left or right, it will take 1 unit time. Also, he can choose to keep still for some time. And of course, he cannot leave the maze. Some treasures exist in the maze. However, it is known that No pains, No gains. There are some guarding points near the treasures. This leads to the fact that every treasure only appears in a certain fixed period of time and it disappears after the time limit. In the meanwhile, every treasure has a certain size, and you may get the treasure by digging out any part of it. The time for digging can be omitted. That is to say, this can be done immediately. According to the information of the people who entered this maze before, Raven knows one specialty of the guarding points---only one treasure can be dug out at one time. Every treasure has a value, and Raven wants to plan a reasonable route so that he can get the highest value. This is the first task, and he needs a perfect beginning.

The first line of the input contains an integer T, which indicates the number of test cases. In the following two rows, there are two positive integers n, m(1 <= n, m <= 20), representing the row and column of the maze. Next there are two numbers, x, y, showing that Raven starts from Row x, Col y at time 0(the top-left point is (0, 0)). The next number p (1 <= p <= 1000) represents the number of treasures. In the following p rows, there are 7 numbers: xi, yi, wi, hi, bi, ei, vi (1 <= wi, hi <= 2, 1 <= ei-bi <= 5). xi and yi represent the row and column of the top left corner of the treasure; wi and hi represent the length and width of the treasure; bi and ei represent the appearing time and disappearing time of the treasure; and vi represents the value of the treasure. This is to say, at any time t within bi <= t < ei range, arriving at any cell (x, y)( xi <= x < xi+wi, yi <= y < yi+hi) may get the treasure. Input should make sure that only one treasure appears at one time.

For each case, output a number to represent the largest total value of the treasure that can be dug out.

2
20 20
0 0
1
0 0 2 2 0 5 100
20 20
0 0
3
2 2 1 1 0 5 100
2 2 1 1 5 6 500
10 10 1 1 20 21 5000

100
5100

Sample 1: Raven can dig out this treasure at time 0. Sample 2: Treasures can be lapped over, but Raven can only dig out the one that appears at that time.