Good Grass

Interview

Time limit1sMemory limit128 MB

Summary
Find the 3x3 subgrid with the largest sum in a grid of milk values and report that sum with the upper-left corner, breaking ties by smallest row then column.
Level

Easy3 of 10

Topics
Array, Prefix sum, Brute force, Implementation
Solved
No attempts yet

Problem

Bessie believes that somewhere in her pasture there is a patch of very special grass, the best grass on earth. Cows that eat it produce more milk.

The pasture is a fully populated rectilinear grid with NRNR rows and NCNC columns, with one cow in every cell, where 3≤NR≤1003 \le NR \le 100 and 3≤NC≤1003 \le NC \le 100. The milk production of the cow in cell (r,c)(r, c) is PrcP_{rc}, with 1≤Prc≤1001 \le P_{rc} \le 100.

Bessie wants to locate the special grass by finding the 3×33 \times 3 square of cells whose total milk production is the largest.

Among all 3×33 \times 3 squares in the grid, find the one whose nine cells have the greatest sum, and output that sum together with the position of its upper-left cell (row first, then column). Rows and columns are numbered starting from 1.

If several 3×33 \times 3 squares share the same greatest sum, output the one with the smallest row number. If there is still a tie, output the one with the smallest column number.

Input

  • Line 1: Two space-separated integers NRNR and NCNC.
  • Lines 2 through NR+1NR+1: Line r+1r+1 contains NCNC space-separated integers representing row rr of the pasture grid.

Output

  • Line 1: A single integer, the greatest possible sum of a 3×33 \times 3 square.
  • Line 2: Two space-separated integers, the row and column of the upper-left corner of the best 3×33 \times 3 square.

Examples1

  1. Example 1

    Input
    6 5
5 6 7 4 6
7 7 8 6 5
9 9 8 3 5
8 8 7 6 4
4 5 2 4 5
3 4 2 3 4
    Expected output
    71
2 1