|
|
|
|
背景 Background |
|
|
|
小杉找到了做棉花糖的最优方案，想去摘云朵，可是摔死了……
他来到了天堂。
天堂当然是很大的，也是很缭乱的。
小杉看到一块路标，写着“天堂的馈赠”。
|
|
|
|
|
|
|
|
描述 Description |
|
|
|
考虑到小杉刚死没多久，为了安抚他受创的心灵和思恋的感情，
天堂派出一个天使给小杉送礼，但IQ不够高的小杉可不能够拿到好礼物。
馈赠在天堂门口进行。天使站在云端，往下扔礼物。
天堂之门的宽度为W格（按1..W编号），高度为0格，云端的高度为H格，小杉只能站在格子里。
开始时（第0秒），小杉站在天堂之门的第P格。
馈赠开始后，天使会在某些时刻从云端的某格扔礼物下来，礼物下落的速度（格/秒）是不一样的。
小杉左右移动去接礼物（每秒可以移动1格或不移动）。
礼物之间的价值当然是不一样的，小杉事先知道了每个礼物的价值。
当礼物在某一秒末恰好到达小杉所在的格子中，小杉就接到了这个礼物。
小杉想知道，他最多可以拿到价值为多少的礼物。
而且，由于礼物下落的速度有些可以很……，小杉还想知道是不是有些礼物他怎么样也拿不到。 |
|
|
|
|
|
|
|
输入格式 Input Format |
|
| |
每组测试数据的
第一行有四个数W，P，H，N(1<=P<=W<=500)，(1<=H<=500)，(0<=N<=3000)
接下来N行，每行四个数t，r，v，s(0<=t<=1500)，(1<=r<=W)，(1<=v<=H)，(|s|<=1e5)
表示天使在t时刻，云端的第r格，以v格/秒的速度扔下价值s的礼物
输入均为正整数
10%的数据W<=100,H<=100,N<=200
|
|
|
|
|
|
|
|
输出格式 Output Format |
|
| |
对每组测试数据输出两行。
第一行仅有一个整数，表示小杉最多能拿到价值多少的礼物。
第二行也仅有一个整数，表示小杉不可能拿到的礼物总价值多少。 |
|
|
|
|
|
|
|
时间限制 Time Limitation |
|
|
|
每个测试点1s |
|
|
|
|
|
|
|
注释 Hint |
|
|
|
注意：当礼物在某一秒末 恰好 到达小杉所在的格子中，小杉才能接到这个礼物。 |
|
|
|
|
|
|
|
|
Flag |
|
题号 |
P1235 |
|
其它 |
通过 |
0人 |
提交 |
0次 |
通过率 |
0% |
难度 |
3 |
|
|
|
|
|
|
