背景

:::epigraph 准备…种植…植物！ :::

题目描述

奶龙的假期沉迷于星露谷物语，为了完成全成就，他需要很多金币购置黄金时钟，他现在急需金币。

在《星露谷物语》这个游戏中玩家可以种植不同的作物，通过种植作物，玩家奶龙可以赚取他所需要的金币。

现在是春季的第 $1$ 天清晨，春季总共持续 $k$ 天，奶龙有一些可耕种的耕地，初始状态它们是空闲的，他手头有 $10^{10^{100}}$ 的金币，现在他开始进行春季的劳作。

皮埃尔的商店总共出售 $n$ 种单次种植型作物的种子，$m$ 种持续产出型作物的种子，它们的定义如下：

• 单次种植型作物，种子价格每份 $p$ 金币，成熟作物售价每份 $q$ 金币，成熟时间为 $t$ 天，也就是在第 $i$ 天种下的作物会在第 $i + t$ 天变为可收获，收获后该作物将会被移除，耕地将变为空闲。
• 持续产出型作物，种子价格每份 $p$ 金币，成熟作物售价每份 $q$ 金币，成熟时间为 $t$ 天，也就是在第 $i$ 天种下的作物会在第 $i + t$ 天变为可收获。同时该作物具有一个收获周期 $s$ 天。收获后该作物将不会被移除，且在第 $j$ 天进行收获的作物将会在 $j + s$ 天再次变为可收获。
• 到了第 $k+1$ 天，春季将落下帷幕，夏季将到来，所有在耕地内的作物都会枯萎，它们不能被收割，即使它们当天本会成熟。

由于奶龙比较懒，在整个春季中，奶龙至多只会从这 $n + m$ 种作物中选择一种作物的种子进行播种；一旦选择了某种作物，则整个春季都不会再种植其他种类的作物。

奶龙每天可以做任意次下面的操作，在同一天内，这些操作的先后顺序可以任意安排；若某块耕地当天因收获而变为空闲，则当天仍可再次播种：

• 从皮埃尔的种子商店购买种子。
• 在空闲的耕地上播种一份种子。
• 收获“可收获”状态的作物一份，并将其出售。
• 注意你不能把土地上现有的作物移除，除非是一次性作物被收获。

因为所有的可种植区域都是等效的，他想知道，单块耕地在春天结束时最多能给他带来多少金的利润。

注意，如果无论如何都无法产生利润，奶龙可以什么都不做，并在春天结束时获得 $0$ 金的利润。

输入格式

第一行输入一个整数 $T\ (1 \le T \le 10^5)$，表示测试数据的数量。

每组测试数据第一行输入 $3$ 个整数 $n, m$ 和 $k\ (1 \le n + m \le 10^5, n \ge 0, m \ge 0, 2 \le k \le 10^9)$，表示单次种植型作物的种类数、持续产出型作物的种类数和春季持续的天数。

随后 $n$ 行输入 $3$ 个整数 $p, q, t\ (0 \le p, q \le 10^9, 1 \le t \le k - 1)$，表示一种单次种植型作物的种子价格，成熟作物售价和成熟时间。

随后 $m$ 行输入 $4$ 个整数 $p, q, t, s\ (0 \le p, q \le 10^9, 1 \le t, s \le k - 1)$，表示一种持续产出型作物的种子价格，成熟作物售价，成熟时间和收获周期。

保证所有测试数据输入中的 $\sum(n + m) \le 3 \times 10^5$.

输出格式

对于每组测试数据，一行输出一个整数表示单块耕地在春天结束时最多能给他带来多少金的利润。

3
2 1 10
20 50 3
5 7 1
30 15 2 2
0 2 7
10 4 2 1
25 9 1 2
1 1 5
10 8 2
5 1 4 1

90
10
0

提示

样例 1 解释

对于第 $1$ 组数据，我们有如下的作物：

我们考虑选择作物 A，如下是一种可行的方案：

总计利润为 $-60 + 50 + 50 + 50 = 90$ 金。