c++

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#include <queue>

using namespace std;

const int N = 1010;

int n, m, p;
int s[N][N], cost[N];
int f[N], g[N][N];

struct Node
{
int v, i, j;
bool operator< (const Node& W) const
{
return v < W.v;
}
};

priority_queue<Node> heap[N];

int get(int x)
{
x %= n;
if (x <= 0) x += n;
return x;
}

int main()
{
scanf("%d%d%d", &n, &m, &p);
for (int i = 1; i <= n; i++)
for (int j = 1; j <= m; j++)
scanf("%d", &s[i][j]);

for (int i = 1; i <= m; i++)
    for (int j = 1; j <= n; j++)
        if (j == 1) s[j][i] += s[n][i - 1];
        else s[j][i] += s[j - 1][i - 1];

memset(f, -0x3f, sizeof f);
memset(g, -0x3f, sizeof g);
f[0] = 0;

for (int i = 1; i <= n; i++) scanf("%d", &cost[i]);
for (int i = 1; i <= n; i++)
{
    g[0][i] = -cost[get(i + 1)];
    heap[get(0 - i)].push({ g[0][i], 0, i });
}

for (int i = 1; i <= m; i++)
{
    for (int j = 1; j <= n; j++)
    {
        auto& h = heap[get(i - j)];
        while (h.size())
        {
            auto t = h.top();
            if (i - p > t.i) h.pop();
            else
            {
                f[i] = max(f[i], s[j][i] + t.v);
                break;
            }
        }
    }
    for (int j = 1; j <= n; j++)
    {
        g[i][j] = f[i] - s[j][i] - cost[get(j + 1)];
        heap[get(i - j)].push({ g[i][j], i, j });
    }
}

int res = 0;
for (int i = 0; i <= m; i++) res = max(res, f[i]);
cout << res << endl;
return 0;

}