272. [NOI 1998]免费馅饼

【题目描述】

$SERKOI$最新推出了一种叫做“免费馅饼”的游戏:

游戏在一个舞台上进行。舞台的宽度为 $W$ 格，天幕的高度为 $H$ 格，游戏者占一格。开始时游戏者站在舞台的正中央，手里拿着一个托盘。下图为天幕的高度为 $4$ 格时某一个时刻游戏者接馅饼的情景。

游戏开始后，从舞台天幕顶端的格子中不断出现馅饼并垂直下落。游戏者左右移动去接馅饼。游戏者每秒可以向左或向右移动一格或两格，也可以站在原地不动。

馅饼有很多种，游戏者事先根据自己的口味，对各种馅饼依次打了分。同时，在$8-308$电脑的遥控下，各种馅饼下落的速度也是不一样的，下落速度以(格/秒)为单位。

当馅饼在某一秒末恰好到达游戏者所在的格子中，游戏者就收集到了这块馅饼。

写一个程序，帮助我们的游戏者收集馅饼，$使得所收集馅饼的分数之和最大$。

【输入格式】

输入文件的第一行是用空格隔开的两个正整数，分别给出了舞台的宽度$W$（$1$到$99$之间的奇数）和高度$H$（$1$到$100$之间的整数）。

接下来按馅饼初始下落时间顺序给出了所有馅饼的信息。每一行给出了一块馅饼的信息，由四个正整数组成，分别表示：馅饼的初始下落时刻（$0$到$1000$秒）、水平位置、下落速度（$1$到$100$）以及分值。馅饼数目不超过$200$。游戏开始时刻为$0$。从$1$开始自左向右依次对水平方向的每格编号。

输入文件中同一行相邻两项之间用一个或多个空格隔开。

【输出格式】

输出文件的第一行给出了一个正整数，表示你的程序所收集的最大分数之和。

其后的每一行按时间顺序给出了游戏者每秒的决策。输出 $0$ 表示原地不动、$1$ 或 $2$ 表示向右移动一步或两步、$-1$ 或 $-2$ 表示向左移动一步或两步。输出应持续到游戏者收集完他要收集的最后一块馅饼为止。

注意：

1.输出数字的字典序最小的方案。

2.馅饼可以掉到高度小于$1$的格子（例：速度为$5$的馅饼，从高度$4$处掉到高度$-1$处，而不是高度$1$）

【样例输入】

3 3
0 1 2 5 
0 2 1 3
1 2 1 3
1 3 1 4

【样例输出】

12
-1
1
1

【来源】

$NOI$