Problem Statement:

Ramesh lives in a village with 5 goldsmiths.

• These goldsmiths in the village only sell gold in the form of gold-biscuits
• The weight of a gold biscuit is M grams (say 1 grams)
• The total quantity offered for sale by different goldsmiths could vary
• Different goldsmiths have different prices per-gold-biscuit-prices at which they sell (i.e. goldsmith1 could be offering 29800 rupees while goldsmith2 could be offering 29805 rupees for the same quantity)

Now Ramesh got a job in Mumbai, where he found 5 other goldsmiths.

• These goldsmiths in the city only buy gold in the form of gold-bars
• The weight of a gold bar is N grams (say 10 grams)
• The total quantity offered for purchase by different goldsmiths could vary
• Different goldsmiths have different per-gold-bar-prices at which they sell (i.e. goldsmith1 could be bidding 29900 rupees while goldsmith2 could be bidding 29905 rupees for the same quantity)

He then created one table for prices of village goldsmiths and city goldsmiths in sorted order - village goldsmiths in ascending order and city goldsmiths in descending order where he mentions the prices per 10 gram of gold.
Based on differences in buying prices in the city and selling prices in the village he trades at both locations to make a profit (if the difference in prices is more than the melting and transportation cost).

For e.g., if City_Goldsmith1 is ready to buy 1 bar ( 1 * N, i.e. 10 grams ) at 29805 rupees per 10 gram while the Village_Goldsmith2 is ready to sell 10 biscuits ( 10 * M, i.e. 10 grams ) at 29800 rupees per 10 gram. In this case, he can sell the same weight to the City_Goldsmith1 at Rs. 29805 and buy the same weight from Village_Goldsmith2 at Rs. 29800, making a profit of 5 rupees.

Now, he wants you to write a program which maximizes his total profit from the buying and selling with the following constraints :

1. For one combination of trade: buying quantity should always be equal to selling quantity by weight ( e.g.. 10 grams would means 10 M and 1N )
2. Maximum quantity to buy or sell is Q grams in one trade
3. Trade only when individual transaction profit is greater than cost C ( transportation etc.)

Example:

If city goldsmiths takes gold in bars (of weight N=10 gms) and village goldsmith takes biscuits (of weight M=1 gms) and the cost of transportation+melting is 65 (C)

           City_Bar_Qty, City_Price     Village_Prices, Village_Biscuits_Qty
Goldsmith1          36   278300               278100    4
Goldsmith2          66   278200               278200    40
Goldsmith3          0       0                300000    0
Goldsmith4          0       0                999999    0
Goldsmith5          0       0                999999    0

• If a particular goldsmith is not interested in buying (or selling) then the qty would be specified as 0 for that goldsmith. In such a case, ignore the corresponding price for that goldsmith.
• Prices are mentioned in per 10 grams for both village and city goldsmiths

Ramesh sees that if he buys 40 biscuits of gold from village (40gms at an average price of 278190.0) and sells an equal quantity of 4 gold bars (40gms at an price of 278300). He would make a profit of 110 rupees per bar which is greater than the cost C. Since, traded 4 bars in exchange of 40 biscuits, his total profit would be 440 rupees (4*110). If he tries to increase the quantity, further transaction's profit would be less than minimum cost. You need to output the price offered by last goldsmith from whom you bought and sell.

So, your average price of buying is 278190. You’ll first buy from Goldsmith1 offering lower price (4 gold biscuits at rs 278100 from goldsmith1) then 36 gold biscuits from Goldsmith2. Your output will be the price of goldsmith2 (i.e. 278200). Similarly for the sell side, output the price of last goldsmith, i.e. 278300.

Input:

First line contains the number of test cases T. First line of each test case contains N and M. Next line contains the maximum quantity to buy/sell Q and cost C. Next five lines contain the table created by Ramesh in sorted order for all goldsmiths in the following format:

<city_goldsmith_qty> <city_goldsmith_price> <village_goldsmith_price> <village_goldsmith_qty>

Output:

For each test case, output the following:

<sold_price_of_last_goldsmith> <bought_price_of_last_goldsmith> <grams_of_gold_traded>

If you are not making any profit, output bought/sold price and quantity of gold as zero.

Constraints

1 <= T <= 100000
N,M,Q,C are 32-bits integers.