P2317 [HNOI2005] Interstellar Trade

$\text{Coke}$ is a shrewd small merchant. This time he wants to boldly engage in interstellar trade. He chooses a trade route specified by the Galactic Trade and Traffic Authority, starting from Earth and passing in order through $Star_1, Star_2, \cdots, Star_N$. The route ends at $Star_N$ (where $\text{Coke}$ will go sightseeing). The planets in the galaxy operate under a planned economy. To sell goods on a planet, you must have that planet’s license. The licenses $\text{Coke}$ holds allow him to sell exactly the quota amount $A_i$ tons of goods on $Star_i$ with $1 \le A_i \le 100$ (neither more nor less; of course, he may choose not to sell anything on $Star_i$). After selling, he can obtain income $B_i$ with $0 \le B_i \le 50000$. Because his private spaceship has limited payload, this shrewd merchant must carefully plan which planets to sell on. The spaceship uses an antimatter propulsion system and requires antimatter fuel. Antimatter fuel is not used to maintain ordinary flight (there is no drag in space); it is used for acceleration when leaving a planet and deceleration when arriving at a planet. Each acceleration and each deceleration consumes one unit of antimatter fuel. Furthermore, for such a long trip, the spaceship must stop en route at some planets to replenish antimatter fuel and to perform regular maintenance (maintenance can only be done on planets). Due to different levels of technological development, the price of antimatter fuel and the maintenance cost vary from planet to planet. In addition, the Galactic Trade and Traffic Authority is hosting a small-merchant trade competition, with generous rewards for the merchant with the highest trade revenue (i.e., total trade income). Therefore, $\text{Coke}$ decides to spare no expense to maximize his trade revenue. Of course, while maximizing trade revenue, as a merchant he still hopes the net profit is as large as possible (net profit = trade revenue − fuel cost − maintenance cost). Assume that when departing from Earth, the spaceship has just been maintained and its fuel tank is full. Whenever the spaceship stops at a planet to sell goods or to refuel, or when it arrives at the terminal for sightseeing, it will undergo maintenance there once. $\text{Coke}$ wants you to devise a plan that meets his requirements.

The first line contains four positive integers $N, M, R, L_0$. - $N$ ($1 \le N \le 2000$) is the number of planets on the route this time. - $M$ ($1 \le M \le 2000$) is the spaceship’s maximum cargo capacity. - $R$ ($0 \le R \le 10000000$) is the maximum amount of fuel the spaceship can carry. - $L_0$ ($1 \le L_0 \le 100$) is the maximum distance the spaceship can fly without maintenance. The next $N$ lines (lines $2$ to $N+1$) each describe a planet. Line $i+1$ contains five non-negative integers $A_i, B_i, L_i, P_i, F_i$: - $A_i$ ($1 \le A_i \le 100$) is the sale quota (tons) on $Star_i$. - $B_i$ ($0 \le B_i \le 50000$) is the income from selling on $Star_i$. - $L_i$ ($1 \le L_i \le 100$) is the distance from Earth to $Star_i$ along the route $Earth \to Star_1 \to Star_2 \to \cdots \to Star_i$. - $P_i$ ($0 \le P_i \le 1000$) is the price per unit of antimatter on $Star_i$. If $P_i = 0$, this planet does not yet have antimatter manufacturing technology. - $F_i$ ($0 \le F_i \le 10000$) is the maintenance cost on $Star_i$. Assume the input satisfies: for $i < j$, it always holds that $L_i < L_j$, and there is exactly one way to achieve the maximum trade revenue.

If such a plan exists, output two integers $X$ and $Y$ separated by a space. $X$ is the maximum trade revenue, and $Y$ is the net profit. If the trip cannot be completed, output “Poor Coke!”.

Translated by ChatGPT 5