409666: GYM103677 D Grape Field

In order to make raisins, Farmer Joe has a $$$r$$$ x $$$c$$$ grape field that consists of $$$r \cdot c$$$ patches of grass. Each patch of grass has a certain number of grapes in it at the end of the harvest. When it is time to harvest, Farmer Joe will start in the top left patch of grass. He will collect all grapes from this patch of grass, add them to a container (will start as container 0), and will continue moving right. He will repeat this process and add the grapes to container 1, 2, 3, etc. Once he has finished packaging the grapes from the top right patch of grass, he will continue this process but move downwards until he hits the bottom right patch of grass. He will then continue moving left, and then upwards. Once he has visited a patch of grass, he will never come to it again. For example, when Joe is traversing upwards on the left side of the field, he will turn right again once he reaches the second row (as he has already visited the first row). He will continue in this spiraling motion until he has packaged all grapes.

Farmer Joe is now ready to sell his grapes to Sun-Maid. However, Sun-Maid is very picky. They will buy all the grapes in container 0, container $$$k$$$, container $$$2k$$$, etc. More generally, they will buy a container if the container number $$$mod$$$ $$$k = 0$$$. How many grapes will Farmer Joe sell to Sun-Maid?

The first line will consist of 3 integers. The first integer will be $$$r$$$ $$$(1 \leq r \leq 50)$$$. The second integer will be $$$c$$$ $$$(1 \leq c \leq 50)$$$. Finally, the last integer will be $$$k$$$ $$$(1 \leq k \leq 20)$$$. The next $$$r$$$ lines will contain $$$c$$$ integers (ranging from 1 to 1000 inclusive) representing each row of the grape field.

Output the number of grapes that Farmer Joe will sell to Sun-Maid.

3 3 2
1 3 4
3 1 4
5 7 2

13

In the first test case, Joe will sell grass patches that have 1, 4, 2, 5, and 1 grapes. The sum of these numbers is 13.