题目描述

在游戏天天酷跑中，最爽的应该是超级奖励模式了吧，没有一切障碍，可以尽情的吃金币，现在请你控制游戏角色来获得尽可能多的分数。游戏界面离散为一个长度为 $1 \sim n$，高度为 $1 \sim m$（初始点为 $(0,1)$）的矩阵图。每个格子上都有收益 $(-1 \sim 1000)$，$-1$ 表示该点不能通过。游戏角色从起点一路奔跑向终点，中途可以跳跃来获得更高的分数，在空中还能进行连跳。

游戏开始前你可以设定跳跃的高度，以及能连跳的次数，初始跳跃高度为 $1$，连跳数为 $1$（最多为 $5$），升级跳跃高度和连跳都需要一定的花费。跳跃高度设定完后游戏角色每次跳跃高度都将固定，连跳必须在下落过程中可以使用。所有操作都将在整点上完成，需要保证设定完的跳跃高度及连跳数，无法跳出游戏高度上限。

从 $(1,1)$ 点用一次跳跃，一次经过 $(2,2),(3,3),(4,2),(5,1)$。

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

从 $(1,1)$ 起跳，依次经过 $(2,2),(3,3),(4,2)$ 再使用连跳，经过 $(5,3),(6,4),(7,3),(8,2),(9,1)$。

输入格式

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

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

输出格式

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

数据范围与约定

对于 $20 \%$ 的数据，满足 $m=2$，$1 \le n \le 10 ^ 5$。

对于另外 $80 \%$ 的数据，$1 \le n \le 10000$，$2 < m \le 20$，其中有 $20\%$ 的数据保证 $2 < n \le 10$，$1 \le m \le 10$。

## 题目描述

在游戏天天酷跑中，最爽的应该是超级奖励模式了吧，没有一切障碍，可以尽情的吃金币，现在请你控制游戏角色来获得尽可能多的分数。游戏界面离散为一个长度为 $1 \sim n$，高度为 $1 \sim m$（初始点为 $(0,1)$）的矩阵图。每个格子上都有收益 $(-1 \sim 1000)$，$-1$ 表示该点不能通过。游戏角色从起点一路奔跑向终点，中途可以跳跃来获得更高的分数，在空中还能进行连跳。

游戏开始前你可以设定跳跃的高度，以及能连跳的次数，初始跳跃高度为 $1$，连跳数为 $1$（最多为 $5$），升级跳跃高度和连跳都需要一定的花费。跳跃高度设定完后游戏角色每次跳跃高度都将固定，连跳必须在下落过程中可以使用。所有操作都将在整点上完成，需要保证设定完的跳跃高度及连跳数，无法跳出游戏高度上限。

![](https://cdn.luogu.com.cn/upload/pic/17609.png) 

从 $(1,1)$ 点用一次跳跃，一次经过 $(2,2),(3,3),(4,2),(5,1)$。

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

![](https://cdn.luogu.com.cn/upload/pic/17610.png)

从 $(1,1)$ 起跳，依次经过 $(2,2),(3,3),(4,2)$ 再使用连跳，经过 $(5,3),(6,4),(7,3),(8,2),(9,1)$。

![](https://cdn.luogu.com.cn/upload/pic/17611.png)

## 输入格式

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

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

## 输出格式

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

### 数据范围与约定

对于 $20 \%$ 的数据，满足 $m=2$，$1 \le n \le 10 ^ 5$。

对于另外 $80 \%$ 的数据，$1 \le n \le 10000$，$2 < m \le 20$，其中有 $20\%$ 的数据保证 $2 < n \le 10$，$1 \le m \le 10$。