Comet OJ

C0998 [HNOI2005]星际贸易

内存限制：256 MB 时间限制：1000 ms

题目描述

Coke 是一个精明的小商人。这次他想大胆地做一次星际贸易。于是他选定了银河贸易交通局所给定的一条贸易路线，从地球出发，依次经过 $Star_1,Star_2,...,Star_N$。贸易路线在 $Star_N$ 结束（Coke 最后要在 $Star_N$ 上观光旅游）。

银河系中各个星球实行计划经济。在一个星球上出售商品，必须获得那个星球的许可证。Coke 手中的许可证允许他在 $Star_i$ 上出售指定配额量 $A_i$（$1 \le A_i \le 10^9$）吨的商品（而且既不能多也不能少，当然他可以不在 $Star_i$ 上出售任何商品），出售后能够获得 $B_i$（$0 \le B_i \le 50000$）的收入。由于 Coke 的私人飞船载重有限，这个精明的小商人不得不好好计划一下他应该向哪些星球出售商品。

飞船采用反物质推进系统行驶，需要反物质燃料。反物质燃料不是用来维持平常飞行的（宇宙间没有阻力），而是用于飞船从星球出发时加速以及飞船到达星球时减速所需的消耗。每次加速和减速各消耗一个单位的反物质燃料。

另外，作如此长距离的飞行，飞船显然要在中途停靠并在某些星球上补充反物质燃料以及对飞船定期进行一些维护（维护职能在星球上进行）。由于各星球之间科技发展水平不等，在各个星球上反物质燃料的售价以及维护飞船的费用是不同的。

此外，银河贸易交通局正在举办小商人贸易竞赛，对于贸易额（即总贸易收入）得到冠军的商人有丰厚的奖赏，因此 Coke 决定不惜血本，要使自己的贸易额达到最大。当然，在贸易额最大的同时，作为一个商人，他还是希望净利润尽可能大（净利润=贸易额-燃料费用-维护费用）。

假设从地球出发时飞船刚刚维护过并装满了燃料，并且飞船每次停靠一个星球出售商品或补充反物质燃料或在终点站观光旅游时就会在那里做一次维护。Coke 希望你给他制定一个方案。

输入格式

第 $1$ 行为 $4$ 个整数 $N,M,R,L_0$。$N$（$1 \le N \le 2000$）表示 Coke 这次要行经的星球数，$M$（$1 \le M \le 2000$）表示飞船最大的载重量，$R$（$0 \le R \le 10^9$）表示飞船最多能携带的燃料数。$L_0$（$1 \le L_0 \le 10^9$）表示飞船不做维护所能飞行的最大距离。

第 $2...N+1$ 行是对每个星球的描述。其中第 $i+1$ 行有 $5$ 个非负整数 $A_i,B_i,L_i,P_i,F_i$。$L_i$（$1 \le L_i \le 10^9$）表示从地球一次经过 $Star_1,Star_2,...,Star_{i-1}$ 最后到达 $Star_i$ 的距离。P_i（0 \le P_i \le 1000）为星球 $Star_i$ 上一个单位反物质的价格，若 $P_i$ 为 $0$，则说明这个星球还没有制造反物质的技术。$F_i$（$0 \le F_i \le 10000$）表示飞船在 $Star_i$上做维护所需要的费用。假设输入数据满足：对于 $i<j$，一定有 $L_i < L_j$，并使得只有一种获得最大贸易额的方法。

输出

如果可以找到这样的方案，那么输出包含两个整数 $X$ 和 $Y$。$X$ 表示贸易额，$Y$ 表示净利润并且两个数字之间用一个空格隔开。如果不能完成这次星际贸易，那么输出 “Poor Coke!”（不包括引号）。

样例

样例输入 1

6 3 10 4
1 2 1 1 1
1 2 2 2 1
1 2 3 9 1
1 1 4 0 1
1 1 5 0 1
1 1 6 1 1

样例输出 1

6 2

提示