there are n places in hackerland and a delivery person can visit the places in exactly m days. The delievery person can start from any of the n places and gets an extra profit for visiting a place . Given a matrix profit of dimensions n*m , if the jth visit of the delievery person is at ith place , the profit increases by profit[i][j]. If the delievery person is currently at ith place , the next place that can be reached is between i-k and i+k . in other words the delievery person can travel to places that are at most k units distance from current place in one day. note that a place can be visited multiple times. determine the maximum profit the delievery person can make by visiting the places optimally over m.

example : n=3,m=3,k=1 profit=[[1,3,1],[2,3,1],[1,1,4]] ans : 8

Explanation- The delivery person can go to any location on day 1. The highest value in the first index is 2 found at location 2. Try starting there. The next day, locations 1 or 3 can be visited. Visit is to location 1, the added profit is 3. This leaves only location 2 within reach for the last day with a profit of 3. The total profit from this route is 2+3+3=8. Visit location 3, the profit is 1. Again, only location 2 can be reached on the last day with a profit of 3. The total profit is 2+1+3=6. Return 8, the maximum possible profit

example 2 — n=3,m=3,k=1 profit =[[1,6,3],[2,4,4],[3,3,1]] ans : 12

Explanation

The journey starts at place 2 which offers a profit of 2. Then the next day the delivery person visits place 1 to get a profit of 6 and on the last day, revisits place 2 to get a profit of 4. Total sum=2+6+4=12

constraints: 1<=n,m<=1e5 , 2<=n*m<=2*1e5 , 1<=k<=n , 1<=profit[i][j]<=1e9