Classroom Attention

Time limit1sMemory limit1024 MB

Summary
Given a grid of digits, find the largest possible increase in the sum of each cell's average absolute difference to its orthogonal neighbors after swapping exactly two cells.
Level

Medium7 of 10

Topics
Implementation, Brute force, Math
Solved
No attempts yet

Problem

The class is full of students seated in a grid of rows and columns. Each student is interested, to some degree, in computers and in sports. A student interested only in sports is marked 00; a student interested only in computers is marked 99; every other student is marked with a digit from 11 to 88 according to how strong their interest is.

Students with similar interests chatter among themselves and ignore the teacher. The smaller the difference in interest between two adjacent students, the more they chatter.

A student's attention is defined as the average of the absolute differences between that student's interest and the interests of their neighbours. A neighbour is a student seated directly in front of, behind, to the left of, or to the right of the given student. The class's total attention is the sum of the attention values of all students.

The teacher wants to raise the class's attention by swapping the seats of exactly two students. Determine the maximum amount by which the class's total attention can be increased with a single swap.

Input

The first line contains two integers MM and NN (1≤M≤2001 \le M \le 200, 1≤N≤2001 \le N \le 200), the number of rows and columns in the class. Each of the next MM lines contains exactly NN characters, each a digit from 00 to 99, giving the students' interest levels.

Output

Output the maximum increase in the class's total attention obtainable by swapping the seats of exactly two students, as a fraction in lowest terms. Print it as p/q with gcd⁡(p,q)=1\gcd(p, q) = 1 and q≥1q \ge 1; if the reduced denominator equals 11, print only the integer pp. If no swap can increase the class's total attention, print 00.

Hint

Worked example (on the grid above): the attention of the student in row 2, column 4 (interest 77) is (∣7−1∣+∣7−3∣+∣7−8∣)/3=(6+4+1)/3=11/3(|7-1| + |7-3| + |7-8|)/3 = (6+4+1)/3 = 11/3. The class's total attention is 93/293/2.

The best move is to swap the student in row 1, column 3 with the student in row 3, column 4; this raises the class's total attention by 34/334/3.

Examples3

  1. Example 1

    Input
    3 4
    6021
    1937
    3138
    
    Expected output
    34/3
    
  2. Example 2

    Input
    3 2
    81
    75
    60
    
    Expected output
    5
    
  3. Example 3

    Input
    3 3
    392
    332
    146
    
    Expected output
    9/2