## LCC '23 Contest 3 S3 - Snowing

View as PDF

Points: 10
Time limit: 3.0s
PyPy 3 15.0s
Python 3 15.0s
Memory limit: 512M
PyPy 3 1G
Python 3 1G

Author:
Problem type

Snow has been asked to shovel the snow from her driveway (how ironic). Her driveway is an by metre grid, where each square metre has a uniform snow height of cm.

Before clearing the driveway of snow, Snow decides to play a little game. She wants to take a picture for her photography instagram account, but she doesn't like how the snow on her driveway looks. In order for Snow to be satisfied with her driveway, the difference in snow heights between adjacent square metres (including diagonal!) must not exceed cm.

To achieve this aesthetic, Snow will use her precision shoveling skills to remove exactly cm of snow from one square metre at a time. Because it must be so precise, it takes her minute each time.

Given how her driveway looks right now, determine the minimum amount of time it would take for Snow to be satisfied with her driveway.

#### Input Specification

The first line will contain integers and .

The next lines will contain space-separated integers, .

#### Output Specification

Output one integer, the minimum amount of time it would take for Snow to be satisfied with her driveway.

#### Sample Input

4 4
4 5 3 4
5 6 7 8
3 4 5 5
3 4 5 6

#### Sample Output

11

#### Sample Explanation

After minutes, Snow's driveway will look like this:

4 4 3 4
4 4 4 4
3 4 5 5
3 4 5 6

It can be shown that no other driveway will take as little time to create as this one.