[JLOI2014]天天酷跑

时间限制：20s 空间限制：128MB

题目描述

在游戏天天酷跑中，最爽的应该是超级奖励模式了吧，没有一切障碍，可以尽情的吃金币，现在请你控制游戏角色来获得尽可能多的分数。

游戏界面离散为一个长度为1~n，高度为1~m（初始点为（0，1））的矩阵图。每个格子上都有收益（-1~1000），-1表示该点不能通过。游戏角色从起点一路奔跑向终点，中途可以跳跃来获得更高的分数，在空中还能进行连跳。游戏开始前你可以设定跳跃的高度，以及能连跳的次数，初始跳跃高度为1，连跳数为1（最多为5），升级跳跃高度和连跳都需要一定的花费。跳跃高度设定完后游戏角色每次跳跃高度都将固定，连跳必须在下落过程中可以使用。所有操作都将在整点上完成，需要保证设定完的跳跃高度及连跳数，无法跳出游戏高度上限。

以下是连跳数为2连跳，跳跃高度为2的跳跃方案：

输入格式

第一行四个整数n，m，cost1，cost2。n，m如题意所示，cost1，cost2分别表示每升一级跳跃高度，连跳数所需的花费。

接下来m行，每行n个数。第i行第j个数表示地图中高度为i，长度在第j列处的收益。

输出格式

如果无法跑出终点线，就输出“mission failed”，否则输出一行三个数，分别表示最大收益；及最大收益时，最小的连跳数；最大收益，最小连跳数时，最小的跳跃高度。

样例输入

7 4 6 10

9 4 7 7 4 3 2

18 8 9 4 15 12 4

19 2 4 7 10 18 12

8 1 13 14 16 0 14

样例输出

67 1 2

提示

20%数据满足 m=2， n<=100000;

另有80%数据 n<=10000，2<m<=20，其中20%数据 2<n<=10，m<=10;

题目来源

没有写明来源