← 返回题目列表

Codeforces · 424/D

D. 冬季两项田径

中文机器翻译题面 查看原题

近日,世界奥委会官方声明称,2030年冬奥会将在托木斯克举行。市政府官员决定,全面做好奥运会筹备工作,尽早建成一切必要的奥运设施。首先,将修建冬季两项跑道。

为了建造冬季两项赛道,分配了一块土地,这是一个分为 n × m 个相同正方形的矩形。每个方格都有两个坐标:它所在的行号(从1到n),它所在的列号(从1到m)。每个正方形也以其高度为特征。在运动期间,冬季两项运动员必须从一个方格移动到另一个方格。如果一名冬季两项运动员从较高的方格移动到较低的方格,他就会下降。如果一名冬季两项运动员从较低的方格移动到较高的方格,他就会上升。如果冬季两项运动员在两个高度相同的方格之间移动,那么他在平坦的地面上移动。

冬季两项赛道应该是分配土地上某些矩形区域的边界,冬季两项运动员将在该区域上按顺时针方向移动。众所周知,冬季两项运动员在平地上做一次动作平均需要 tp 秒,上升需要 tu 秒,下降需要 td 秒。托木斯克政府希望选择路线,使冬季两项运动员平均能在尽可能接近 t 秒的时间内通过该路线。换句话说,通过所选轨道的时间ts与t之间的差值应该是最小的。

为了更好地理解,您可以查看输入数据的第一个样本。在这个样本中,n = 6,m = 7,管理部门希望赛道覆盖时间尽可能接近 t = 48 秒,同时 tp = 3,tu = 6 和 td = 2。如果我们考虑图像上箭头所示的矩形,平均冬季两项运动员可以在 48 秒内沿着边界以顺时针方向移动。该轨道的左上角位于行号 4、列号 3 的正方形内,右下角位于行号 6、列号 7 的正方形内。

除其他事项外,政府希望作为冬季两项赛道边界的矩形的所有边由不少于三个正方形组成,并完全包含在选定的土地内。

您将获得给定土地的描述和所有必要的时间值。您将编写程序来找到最适合冬季两项赛道的矩形。如果有多个这样的矩形,则可以打印其中任何一个。

输入

输入的第一行包含三个整数 n、m 和 t (3 ≤ n, m ≤ 300, 1 ≤ t ≤ 109) — 地块的大小和所需的覆盖时间距离。

第二行还包含三个整数 tp、tu 和 td (1 ≤ tp, tu, td ≤ 100) — 冬季两项运动员平均需要分别跑完赛道的平坦部分、上升和下降的时间。

接下来是 n 行,每行包含 m 个整数,用于设置给定土地上每个正方形的高度。每个高度值都是正整数,不超过 106。

输出

在输出的一行中打印四个正整数 - 左上角的行数和列数以及为轨道选择的矩形的右下角的行数和列数。

示例

输入 #1

6 7 48
3 6 2
5 4 8 3 3 7 9
4 1 6 8 7 1 1
1 6 4 6 4 8 6
7 2 6 1 6 9 4
1 9 8 6 3 9 2
4 5 6 8 4 3 7

输出 #1

4 3 6 7