CF424D Biathlon Track

日前，国际奥委会宣布2030年冬季奥运会将在托木斯克举办。托木斯克市政府计划提前建设所有奥运设施，首要任务是建造一条冬季两项滑雪道。 为此，市政府划拨了一块矩形土地，并将其划分为 $ n \times m $ 个相同的方格。每个方格用行号（从1至 $ n $）和列号（从1至 $ m $）来表示。此外，这些方格各有一个高度。比赛中，运动员需要在方格间移动。如果从高处移动到低处，就是下坡；反之，则是上坡；若在两个高度相同的方格间移动，则是平地移动。 滑雪道应围成一个矩形，运动员将沿着这个矩形区域的边界顺时针移动。已知在平地、上坡和下坡上分别需要 $ t_{p} $、$ t_{u} $ 和 $ t_{d} $ 秒。市政府希望选择一条路径，使得运动员经过这条路径的时间尽量贴近 $ t $ 秒。换句话说，经过路径所需的时间 $ t_{s} $ 与 $ t $ 之间差距应尽可能小。 以输入的第一个示例为例，$ n=6 $，$ m=7 $，市政府期望滑雪道的通过时间为 $ t=48 $ 秒，同时，$ t_{p}=3 $，$ t_{u}=6 $ 和 $ t_{d}=2 $。如果选择图中箭头指示的矩形路径，运动员便可沿这个边界顺时针移动恰好用时 $ 48 $ 秒。该路径的左上角起点为第 $ 4 $ 行第 $ 3 $ 列，右下角终点为第 $ 6 $ 行第 $ 7 $ 列。 另外，政府还要求路径围成的矩形每条边必须至少由三个方格构成，并且整体需完全位于分配的土地内部。 你需要根据这块土地的高度信息以及相应的时间参数，编写程序找到最合适的矩形路径。如果存在多个满足要求的矩形，你可以输出其中任意一个。

第一行输入三个整数 $ n $、$ m $ 和 $ t $（$ 3 \leq n, m \leq 300 $，$ 1 \leq t \leq 10^9 $），分别表示土地的规模和期望的通过时间。 第二行输入三个整数 $ t_{p} $、$ t_{u} $ 和 $ t_{d} $（$ 1 \leq t_{p}, t_{u}, t_{d} \leq 100 $），表示运动员在平地、上坡和下坡所需的时间。 接下来 $ n $ 行，每行包含 $ m $ 个整数，表示每个方格的高度，这些高度均为不超过 $ 10^6 $ 的正整数。

在一行中输出四个整数，代表所选矩形路径的左上角和右下角的行号和列号。 **本翻译由 AI 自动生成**