SERKOI最新推出了一种叫做“免费馅饼”的游戏:游戏在一个舞台上进行。舞台的宽度为W格，天幕的高度为H格，游戏者占一格。开始时游戏者站在舞台的正中央，手里拿着一个托盘。下图为天幕的高度为4格时某一个时刻游戏者接馅饼的情景。
游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。
馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时，在8-308电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以格/秒为单位。
当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。
写一个程序，帮助我们的游戏者收集馅饼，使得所收集馅饼的分数之和最大。
输入
输入文件的第一行是用空格隔开的两个正整数，分别给出了舞台的宽度W（1到99之间的奇数）和高度H（1到100之间的整数）。
接下来依馅饼的初始下落时间顺序给出了所有馅饼的信息。每一行给出了一块馅饼的信息。由四个正整数组成，分别表示了馅饼的初始下落时刻（0到1000秒），水平位置、下落速度（1到100）以及分值。游戏开始时刻为0。从1开始自左向右依次对水平方向的每格编号。
输入文件中同一行相邻两项之间用一个或多个空格隔开。
输出
输出文件的第一行给出了一个正整数，表示你的程序所收集的最大分数之和。
其后的每一行依时间顺序给出了游戏者每秒的决策。输出0表示原地不动、1或2表示向右移动一步或两步、-1 或-2表示向左移动一步或两步。输出应持续到游戏者收集完他要收集的最后一块馅饼为止。
样例输入
3 3
0 1 2 5
0 2 1 3
1 2 1 3
1 3 1 4
样例输出
12
-1
1
1
【参考程序】：
#include<cstring>
#include<cstdio>
#include<iostream>
using namespace std;
int F[1010][1010],a[1010][1010],prev[1010][1010];
int n,m,ans,sumt,bx,by;
void cout_path(int bx,int by)
{
if (bx<=0) return ;
cout_path(bx-1,by-prev[bx][by]);
printf("%d\n",prev[bx][by]);
}
int main()
{
freopen("freepizza.in","r",stdin);
freopen("freepizza.out","w",stdout);
scanf("%d%d",&n,&m);
sumt=0;
int t,w,v,s;
memset(a,0,sizeof(a));
while (scanf("%d%d%d%d",&t,&w,&v,&s)!=EOF)
{
if ((m-1)%v==0 || t==0)
{
a[t+(m-1)/v][w]+=s;
if (t+(m-1)/v>sumt) sumt=t+(m-1)/v;
}
}
for (int i=0;i<=sumt;i++)
for (int j=1;j<=m;j++)
F[i][j]=-0x7FFFFFFF;
ans=F[0][(n+1)/2]=a[0][(n+1)/2];
for (int i=1;i<=sumt;i++)
for (int j=1;j<=n;j++)
{
for (int k=2;k>=-2;k--)
if (j-k>0 && j-k<=n && F[i-1][j-k]>F[i][j])
{
F[i][j]=F[i-1][j-k];
prev[i][j]=k;
}
F[i][j]+=a[i][j];
if (F[i][j]>ans)
{
ans=F[i][j];
bx=i; by=j;
}
}
printf("%d\n",ans);
for (int i=1;i<=n;i++)
if (F[sumt][i]>ans)
{
ans=F[sumt][i];
bx=sumt; by=i;
}
if (sumt==0 && ans) printf("0\n");
else cout_path(bx,by);
return 0;
}