↵
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