Interstellar Trade Optimization

Problem Statement: Coke is a shrewd merchant who is venturing into interstellar trade. He will travel a fixed route starting from Earth (index 0) and then stopping at stars Star 1, Star 2, ..., Star N in order. He must finish his journey at Star N (where he will also engage in tourism) and, at every landing, the spaceship undergoes maintenance. On each star i (for 1 ≤ i ≤ N-1), Coke may choose to sell goods. However, due to governmental regulations a license permits him to sell exactly \(A_i\) tons of goods on that star – if he sells, he must sell exactly \(A_i\) tons and will earn a revenue of \(B_i\) (in credits). Coke’s spaceship has a cargo capacity of \(Q\) tons, so the total goods sold (i.e. \(\sum_{i\in S}A_i\) for chosen stars \(S\)) cannot exceed \(Q\).

The spaceship is fuelled by antimatter. It uses 1 unit of fuel for accelerating (takeoff) and another unit for deceleration (landing). Thus, for a direct flight from one star to another the fuel consumption is \(2\times d\) units where \(d\) is the number of segments between the stars. Due to a limited fuel‐tank capacity of \(F\) units, the ship cannot cover arbitrarily long distances without refuelling.

After landing to sell goods or to refuel, the spaceship must undergo maintenance at that star. Different stars sell antimatter fuel at different prices and charge different maintenance fees. In particular, for each star \(i\) (1 ≤ i ≤ N) the fuel price is \(P_i\) (per fuel unit) and the maintenance fee is \(M_i\). Note that at the destination \(Star_N\) (which is only used for tourism) maintenance is mandatory as well. At Earth (index 0), the ship starts with a full tank and has just been maintained.

Coke is also competing in a trade contest where the trade revenue (i.e. the total sales revenue) is the primary criterion for winning. Subject to achieving the maximum possible trade revenue, Coke wants his net profit (defined as total sales revenue minus the total cost, with cost coming from fuel purchases and maintenance fees) to be as high as possible. Refuelling stops may be inserted arbitrarily between mandatory stops (which are the stars where a sale is made and the destination) in order to minimize the extra cost. When refuelling at an intermediate (optional) stop \(k\) (between a previously landed star \(u\) and the next mandatory stop \(v\)), if the distance from \(u\) to \(k\) is \(d = k-u\), then you must pay a cost of \(2d\,P_k\) (because you burn \(2d\) units of fuel and must buy that amount at star \(k\)) and also incur the maintenance fee \(M_k\); then you refuel to full (i.e. \(F\) units) before continuing. However, if the mandatory stop is directly reachable from \(u\) (i.e. if \(2(v-u)\le F\)), you may fly directly with zero extra fuel cost (although upon landing at a mandatory stop you must pay its maintenance fee).

Your task is to help Coke plan his journey. That is, you must decide at which stars (from 1 to N-1) he should sell goods (subject to the cargo constraint \(\sum A_i \le Q\)) so that his total trade revenue is maximized. Among all such selections achieving the maximum trade revenue, you must choose the strategy which minimizes the total extra cost incurred by refuelling and maintenance (this minimization gives the maximum possible net profit). The mandatory stops of the journey are Earth (index 0), all stars at which a sale is made and the destination star \(N\). The extra cost required to travel between two mandatory stops \(u\) and \(v\) is defined as:

\[ \text{cost}(u,v)=\begin{cases} 0,&\text{if }2(v-u)\le F,\\ \min_{u<k<v}\Big\{2(k-u)P_k+M_k+\text{cost}(k,v)\Big\},&\text{otherwise.} \end{cases} \]

The total extra cost of an itinerary with mandatory stops \(r_0=0,\,r_1,\,r_2,\,\ldots,\,r_m=N\) is

[ \sum_{j=0}^{m-1}\Bigl(\text{cost}(r_j,r_{j+1})+M_{r_{j+1}}\Bigr). ]

The net profit is then given by:

\[ \text{Net Profit} = \Bigl(\sum_{i\in S}B_i\Bigr) - \Bigl(\sum_{j=0}^{m-1}(\text{cost}(r_j,r_{j+1})+M_{r_{j+1}})\Bigr). \]

Input: The first line contains three integers \(N\), \(Q\) and \(F\), where \(N\) (\(\ge 2\)) is the number of stars (excluding Earth), \(Q\) (\(\ge1\)) is the cargo capacity in tons, and \(F\) (\(\ge 2\)) is the fuel‐tank capacity (in fuel units). Then \(N\) lines follow. For \(i=1,2,\ldots,N\), the \(i\)th line contains four integers \(A_i\), \(B_i\), \(P_i\) and \(M_i\) where:

• \(A_i\) (1 ≤ \(A_i\) ≤ 100) is the quota (tons) that must be sold if trading at star \(i\) (note that trading is only allowed at stars 1 through \(N-1\); no sale is made at the destination \(N\)).
• \(B_i\) (0 ≤ \(B_i\) ≤ 50000) is the revenue earned if a sale is made at star \(i\).
• \(P_i\) is the price per unit of antifuel at star \(i\).
• \(M_i\) is the maintenance fee charged at star \(i\) when the ship lands.

Output: Output two integers separated by a space. The first is the maximum total trade revenue (i.e. the sum of \(B_i\)’s for the chosen sale stars) obtainable subject to the cargo constraint. The second is the maximum net profit corresponding to that maximum revenue.

Note: It is guaranteed that a solution exists. The optimal refuelling strategy (i.e. the choice of optional stops between mandatory stops) is assumed to be used to minimize the extra cost.

inputFormat

The input begins with a line containing three integers \(N\), \(Q\) and \(F\), as described above. This is followed by \(N\) lines, each containing four integers \(A_i\), \(B_i\), \(P_i\) and \(M_i\) for \(i=1,...,N\). Note that no sale can be made at star \(N\) (the destination).

outputFormat

Output two integers: the maximum trade revenue and the corresponding maximum net profit (i.e. revenue minus total extra cost), separated by a space.

sample

4 5 4
2 100 5 20
3 150 4 30
2 120 6 25
0 0 3 10

270 205