I. Stardew Valley
time limit per test
1 second
memory limit per test
1024 megabytes
input
standard input
output
standard output

Nailong is addicted to Stardew Valley during his holidays. To complete all achievements, he needs a lot of gold coins to purchase the Gold Clock, so he is currently in desperate need of gold coins.

In the game Stardew Valley, players can grow different crops. By growing crops, the player Nailong can earn the gold coins he needs.

It is now the morning of the $$$1$$$st day of Spring, and Spring lasts for $$$k$$$ days in total. Nailong has some arable plots of land, which are initially empty. He has $$$10^{10^{100}}$$$ gold coins on hand, and now he starts his farm work for the Spring.

Pierre's General Store sells $$$n$$$ types of single-harvest crop seeds and $$$m$$$ types of multi-harvest crop seeds. Their definitions are as follows:

  • Single-harvest crop: the seed price is $$$p$$$ gold coins per unit, the selling price of the mature crop is $$$q$$$ gold coins per unit, and the maturation time is $$$t$$$ days. That is, a crop planted on day $$$i$$$ will become harvestable on day $$$i + t$$$. After harvesting, the crop will be removed, and the plot will become empty.
  • Multi-harvest crop: the seed price is $$$p$$$ gold coins per unit, the selling price of the mature crop is $$$q$$$ gold coins per unit, and the maturation time is $$$t$$$ days. That is, a crop planted on day $$$i$$$ will become harvestable on day $$$i + t$$$. At the same time, this crop has a harvest cycle of $$$s$$$ days. After harvesting, the crop will not be removed, and a crop harvested on day $$$j$$$ will become harvestable again on day $$$j + s$$$.
  • On day $$$k + 1$$$, Spring comes to an end and Summer arrives. All crops in the plots will wither and cannot be harvested, even if they were supposed to mature on that day.

Because Nailong is quite lazy, he will choose to plant at most one type of crop throughout the entire Spring.

Nailong can perform the following operations any number of times each day:

  • Buy seeds from Pierre's General Store.
  • Plant a unit of seed on an empty plot of land.
  • Harvest a unit of crop that is in the "harvestable" state and sell it.
  • Note that you cannot remove existing crops from the land unless it is a single-harvest crop being harvested.

Since all arable plots are equivalent, he wants to know the maximum profit in gold coins that each plot of land can bring him by the end of Spring.

Note that if it is impossible to make a profit no matter what, Nailong can choose to do nothing and gain a profit of $$$0$$$ gold coins by the end of Spring.

Input

The first line contains a single integer $$$T$$$ ($$$1 \le T \le 10^5$$$), representing the number of test cases.

The first line of each test case contains 3 integers $$$n$$$, $$$m$$$, and $$$k$$$ ($$$1 \le n + m \le 10^5, n \ge 0, m \ge 0, 2 \le k \le 10^9$$$), representing the number of types of the two kinds of seeds and the number of days Spring lasts.

Each of the following $$$n$$$ lines contains 3 integers $$$p$$$, $$$q$$$, and $$$t$$$ ($$$0 \le p , q\le 10^9, 1 \le t \le k - 1$$$), representing the seed price, mature crop selling price, and maturation time of a single-harvest crop.

Each of the following $$$m$$$ lines contains 4 integers $$$p$$$, $$$q$$$, $$$t$$$, and $$$s$$$ ($$$0 \le p , q\le 10^9, 1 \le t, s \le k - 1$$$), representing the seed price, mature crop selling price, maturation time, and harvest cycle of a multi-harvest crop.

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

Output

For each test case, output a single line with an integer representing the maximum profit in gold coins that each plot of land can bring him by the end of Spring.

Example
Input
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
Output
90
10
0
Note

For the 1st test case, we have the following crops:

CropTypeSeed PriceCrop Selling PriceMaturation TimeHarvest Cycle
ASingle-harvest20503N/A
BSingle-harvest571N/A
CMulti-harvest301522

We consider choosing Crop A. A feasible plan is as follows:

DayActionDaily Balance
1Buy 3 units of Crop A seeds, and plant 1 unit of Crop A-60
4Harvest and sell 1 harvestable unit of Crop A, and plant 1 unit of Crop A50
7Harvest and sell 1 harvestable unit of Crop A, and plant 1 unit of Crop A50
10Harvest and sell 1 harvestable unit of Crop A50

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