I. Madhav's Mega Terrarium
time limit per test
3 seconds
memory limit per test
256 megabytes
input
standard input
output
standard output

Your huge terrarium has a big glass panel. You have several stickers that you can paste onto the glass.

You have $$$n$$$ decorative stickers. For each sticker $$$i$$$ you are given:

  • $$$b[i]$$$ — the beauty provided by the sticker
  • $$$ir[i]$$$ — the amount of IR radiation blocked by the sticker
  • $$$vis[i]$$$ — the amount of Visible Light blocked by the sticker
  • $$$area[i]$$$ — the area of the sticker

You also have $$$m$$$ bottles of UV protecting cream. For each bottle $$$i$$$:

  • $$$u[i]$$$ — the amount of UV radiation blocked by the bottle
  • $$$au[i]$$$ — the area over which the cream must be evenly spread
  • the cream can only be applied on top of decorative stickers (not on the glass directly)
  • one bottle may be split across multiple stickers, but each unit area of a decorative sticker can receive cream from only one bottle
  • if you choose a bottle, you must use all the cream inside it

Example clarification: If you choose bottles 1 and 2, and decorative stickers 2, 4, and 6, then the following must hold: $$$au[1] + au[2] \lt = area[2] + area[4] + area[6]$$$.

Your scientists determine the following:

  • The plants will die if you block more than $$$I$$$ units of IR rays.
  • The plants will die if you block more than $$$V$$$ units of Visible rays.
  • The plants will die if you block less than $$$U$$$ units of UV rays.

Find the maximum total beauty you can obtain. If it is impossible to keep the plants alive, output -1.

Input

The first line contains the integer $$$t$$$ $$$(1 \le t \le 60)$$$, the number of testcases. For each test case we have:

The first line contains five integers $$$n, m, I, V, U$$$.

Then $$$n$$$ lines follow. The $$$i$$$-th of these lines contains four integers: $$$b[i], ir[i], vis[i], area[i]$$$.

Then $$$m$$$ lines follow. The $$$i$$$-th line contains two integers: $$$u[i]$$$, $$$au[i]$$$.

Constraints

Let $$$A_1 = \sum_{i=1}^n area[i]$$$ and $$$A_2 = \sum_{i=1}^n au[i]$$$

  • $$$1 \lt = n, m \lt = 60$$$
  • $$$0 \lt = I, V, U, A_1, A_2 \lt = 150$$$
  • $$$1 \lt = ir[i], vis[i], b[i], area[i], au[i], u[i] \lt = 150$$$

Additionally the following hold:

  • The sum of $$$n,m$$$ across all test cases doesn't exceed 60.
  • The sum of $$$I, V, U, A_1, A_2$$$ across all test cases doesn't exceed 150.
Output

Print a single integer: the maximum achievable total beauty. If it is impossible to keep the plants alive, print -1.

Example
Input
2
3 3 50 3 5
3 2 1 2
4 3 2 3
5 4 10 4
7 1
8 1
10 100
3 2 4 4 3
3 2 1 2
2 1 2 2
4 2 2 3
2 2
3 3
Output
7
7
Note

In the first example test case

  • We see $$$I = 50$$$ and is much higher than our stickers, so we don't need to worry about it.
  • We see $$$V = 3$$$, so selecting sticker 3 is not feasible (it blocks 10 units of visible light)
  • We see $$$U = 5$$$, both bottle 1 and bottle 2 satisfy our requirements, so we can select either bottle (or both). Bottle 3 cannot be selected as it requires at least 100 units of area, which sticker 1 and 2 dont provide.
  • Clearly, we can pick both sticker 1 and sticker 2 in this sutation now. This maximizes our beauty and gives us the answer 7.

The second example test case can also be reasoned out to show that 7 is the best we can do.