Background

:::epigraph Prepare... to plant... crops! :::

Problem Description

Nailong is addicted to Stardew Valley during the holiday. To complete all achievements, he needs a lot of gold to buy the Golden Clock, so he urgently needs money now.

In Stardew Valley, players can plant different crops. By planting crops, player Nailong can earn the gold he needs.

It is the morning of day $1$ in spring. Spring lasts for a total of $k$ days. Nailong has some farmland that can be cultivated; initially, all plots are idle. He has $10^{10^{100}}$ gold in hand, and now he starts working for spring.

Pierre's shop sells $n$ kinds of single-harvest crop seeds and $m$ kinds of regrowable crop seeds. They are defined as follows:

• Single-harvest crops: each seed costs $p$ gold, each harvested crop sells for $q$ gold, and the growth time is $t$ days. That is, a crop planted on day $i$ becomes harvestable on day $i + t$. After harvesting, the crop is removed and the plot becomes idle.
• Regrowable crops: each seed costs $p$ gold, each harvested crop sells for $q$ gold, and the growth time is $t$ days. That is, a crop planted on day $i$ becomes harvestable on day $i + t$. Meanwhile, it has a regrowth cycle of $s$ days. After harvesting, the crop is not removed, and a crop harvested on day $j$ will become harvestable again on day $j + s$.
• On day $k + 1$, spring ends and summer arrives. All crops in the farmland will wither and cannot be harvested, even if they would have matured on that day.

Because Nailong is lazy, throughout the whole spring he will choose at most one crop (among these $n + m$ crops) to plant. Once he chooses a crop, he will not plant any other crop for the rest of spring.

Each day, Nailong may perform the following operations any number of times, and the order of operations within the same day can be arranged arbitrarily. If a plot becomes idle on that day due to harvesting, it can still be planted again on the same day:

• Buy seeds from Pierre's seed shop.
• Plant one seed on an idle plot.
• Harvest one harvestable crop and sell it.
• Note that you cannot remove an existing crop from the land, unless it is a single-harvest crop being harvested.

Since all plantable plots are equivalent, he wants to know the maximum profit (in gold) that a single plot of farmland can bring him by the end of spring.

Note that if no profit can be made no matter what, Nailong can do nothing and obtain a profit of $0$ gold at the end of spring.

Input Format

The first line contains an integer $T\ (1 \le T \le 10^5)$, denoting the number of testdata.

For each testdata, the first line contains three integers $n, m, k\ (1 \le n + m \le 10^5, n \ge 0, m \ge 0, 2 \le k \le 10^9)$, representing the number of single-harvest crops, the number of regrowable crops, and the number of days in spring.

The next $n$ lines each contain three integers $p, q, t\ (0 \le p, q \le 10^9, 1 \le t \le k - 1)$, representing the seed price, the selling price of the harvested crop, and the growth time of a single-harvest crop.

The next $m$ lines each contain four integers $p, q, t, s\ (0 \le p, q \le 10^9, 1 \le t, s \le k - 1)$, representing the seed price, the selling price of the harvested crop, the growth time, and the regrowth cycle of a regrowable crop.

It is guaranteed that $\sum(n + m) \le 3 \times 10^5$ over all testdata.

Output Format

For each testdata, output one integer per line, denoting the maximum profit in gold that a single plot of farmland can bring him by the end of spring.

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

Hint

Sample 1 Explanation

For the first testdata, we have the following crops:

Consider choosing crop A. One feasible plan is as follows:

The total profit is $-60 + 50 + 50 + 50 = 90$ gold.

Translated by ChatGPT 5