Problem Description
Harvest Moon (牧場物語 Bokujō Monogatari) is a virtual role playing game for the Super Nintendo Entertainment System developed and published by Pack-In-Video (now Marvelous AQL), first released in Japan in 1996, and 1997 in North America. This is the first game in the long-running Harvest Moon titles. A PAL version was released by Nintendo in early 1998 for Western Europe and Oceania, with language localizations for Germany and France.
-- wikipedia
Hard though, it's still an incorrigibly temptation for Moor. In the game, Moor's favorite is to cultivate in his own pasture. His pasture is large - we may consider it as a w×h lattice.
The shop sells A kinds of seeds. The price of the ith seed is Q_i dollars, and it can be sowed to cover a 3×3 lattice. Note that the cover area may contain the grids outside his pasture, but only the grids inside belong to him. Further more, although a grid may be sowed multiple times, the later sowing on this grid exert nothing if the corns are still growing in it.
After ploughing and weeding, the corns get ripe right after N_i days and Moor will go harvest. For instance, if Moor sows the seeds at the beginning of day x, they will get ripe at the beginning of the (x+N_i)th day(or you may consider it as the right end of the (x+N_i-1)th day). After harvest, some of the corns will disappear and the grids they belong to would become empty, while the others may stays and get ripe again and again, in a period of M_i days. For convenience, Moor always leaves the second kind of corns staying, but he will try to keep sowing in those new empty grids. Moor only sows seeds and harvest at the beginning or ending of some day, and you may assume it wastes no time for Moor to make operations.
Initially, Moor's got Y dollars. When selling a 1×1 grid of corns, he will obtain P_i dollars back. Moor wonders the maximum dollars he will get at the end of the Dth day, if he buys only one kind of seeds? Certainly, he may do nothing and keep all dollars in his pocket.
Input
The input contains several test cases.
An integer T(T≤110) will exist in the first line of input, indicating the number of test cases.
Each test case begins with 5 integers w,h,A,D,Y(3≤w,h≤100,0<A,D≤1000,0<Y≤100000).
The following A lines, each with 4 integers Q_i,P_i,N_i,M_i (0<Q_i,P_i≤1000;N_i,M_i≤10000), describe the property of the ith seed. M_i=0 denotes that the seed will not get ripe again after harvest.
Output
Output the maximum dollars he's able to obtain at the end of the Dth day, one per line.
Sample Input
1
3 3 2 3 100
100 90 3 0
100 90 2 0
Sample Output
810
