You have an $$$n$$$ by $$$n$$$ square garden which can be thought of as a grid. In each cell, there is either good planting land, a well, or bad planting land. You only want to focus on one gardening strip because it's much easier to maintain. A gardening strip is a $$$2$$$-tall strip that is always horizontal (but can have a variable length), where if you cut out just the gardening strip, all planting land must be at most $$$k$$$ away from the closest well, and all land in the strip is either good planting land or wells. Distance between two cells is defined by: $$$|a.x - b.x| + |a.y - b.y|$$$ (Manhattan distance). Now when trying to choose a gardening strip, you ask yourself, how many gardening strips are in my garden square?
You will be given $$$n$$$ ($$$1 \le n \le 2000$$$) and $$$k$$$ ($$$1 \le k \le n$$$) in the first line. Then in the next $$$n$$$ lines, you will be given $$$n$$$ space-separated integers from $$$1$$$ to $$$3$$$. $$$1$$$ represents good planting land, $$$2$$$ represents a well and $$$3$$$ represents bad planting land.
Additionally, it is guaranteed there are no vertically adjacent wells. In order words, for every well not in the last row, the cell in the next row and the same column is not a well.
Output the number of possible gardening strips.
10 31 1 1 1 2 1 1 3 1 12 1 1 1 1 1 1 2 1 31 1 2 1 1 2 1 3 1 11 1 1 1 1 1 1 1 1 11 2 1 1 1 1 1 1 2 11 1 1 2 1 1 1 1 1 11 1 1 1 1 1 1 1 1 21 2 1 1 1 3 1 1 1 11 3 1 1 1 1 1 2 1 31 1 3 2 1 1 1 1 1 3
140
Example of a good gardening strip:
$$$1$$$ $$$1$$$ $$$1$$$ $$$1$$$ $$$2$$$
$$$2$$$ $$$1$$$ $$$1$$$ $$$1$$$ $$$1$$$
All planting land (all the $$$1$$$s) is at most $$$2$$$ away from the wells (the $$$2$$$s), which is less than $$$k$$$ (which is $$$3$$$).
Example of a bad gardening strip:
$$$1$$$ $$$1$$$ $$$1$$$
$$$1$$$ $$$1$$$ $$$1$$$
There are no wells in the strip, and so none of the planting land is at most $$$k$$$ away from wells.
