#include <bits/stdc++.h>
using namespace std;
struct SegTree {
  int size;
  vector<long long> seg;
  SegTree() {}
  SegTree(int size) {
    this->size = size;
    seg.resize(1 << (size + 1));
  }
  void init() {
    for (int i = 0; i < (1 << (size + 1)); i++) seg[i] = -1e18;
  }
  void update(int i, long long val) {
    i += (1 << size);
    seg[i] = val;
    while (i > 1) {
      i /= 2;
      seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
    }
  }
  long long query(int a, int b, int k, int l, int r) {
    if (b < l || r < a) return -1e18;
    if (a <= l && r <= b) return seg[k];
    long long lval = query(a, b, k * 2, l, (l + r) / 2);
    long long rval = query(a, b, k * 2 + 1, (l + r) / 2 + 1, r);
    return max(lval, rval);
  }
  long long query(int a, int b) {
    if (a > b) return -1e18;
    return query(a, b, 1, 0, (1 << size) - 1);
  }
};
struct LazySegTree {
  int size;
  vector<long long> seg, delay;
  LazySegTree() {}
  LazySegTree(int size) {
    this->size = size;
    seg.resize(1 << (size + 1));
    delay.resize(1 << (size + 1));
  }
  void init() {
    for (int i = 0; i < (1 << (size + 1)); i++) {
      seg[i] = -1e18;
      delay[i] = 0;
    }
  }
  void eval(int l, int r, int k) {
    if (delay[k]) {
      seg[k] += delay[k];
      if (l < r) {
        delay[k * 2] += delay[k];
        delay[k * 2 + 1] += delay[k];
      }
      delay[k] = 0;
    }
  }
  void update(int i, long long val) {
    query(i, i);
    i += (1 << size);
    seg[i] = val;
    while (i > 1) {
      i /= 2;
      seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
    }
  }
  void add(int a, int b, int k, int l, int r, long long val) {
    eval(l, r, k);
    if (b < l || r < a) return;
    if (a <= l && r <= b) {
      delay[k] += val;
      eval(l, r, k);
      return;
    }
    add(a, b, k * 2, l, (l + r) / 2, val);
    add(a, b, k * 2 + 1, (l + r) / 2 + 1, r, val);
    seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
  }
  void add(int a, int b, long long val) {
    if (a > b) return;
    add(a, b, 1, 0, (1 << size) - 1, val);
  }
  long long query(int a, int b, int k, int l, int r) {
    eval(l, r, k);
    if (b < l || r < a) return -1e18;
    if (a <= l && r <= b) return seg[k];
    long long lval = query(a, b, k * 2, l, (l + r) / 2);
    long long rval = query(a, b, k * 2 + 1, (l + r) / 2 + 1, r);
    return max(lval, rval);
  }
  long long query(int a, int b) { return query(a, b, 1, 0, (1 << size) - 1); }
};
long long n, m, k;
long long a[55][20005];
long long sum[55][20005];
long long dp[55][20005];
SegTree seg(15);
LazySegTree seg2(15);
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      sum[i][j] = sum[i][j - 1] + a[i][j];
    }
  }
  seg.init();
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m - k + 1; j++) {
      dp[i][j] = -1e18;
    }
  }
  for (int j = 1; j <= m - k + 1; j++) {
    dp[1][j] = (sum[1][j + k - 1] - sum[1][j - 1]) +
               (sum[2][j + k - 1] - sum[2][j - 1]);
    seg.update(j, dp[1][j]);
  }
  seg2.init();
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= k; j++) {
      seg2.update(j, dp[i][j] - (sum[i + 1][k] - sum[i + 1][j - 1]));
    }
    for (int j = 1; j <= m - k + 1; j++) {
      long long x = (sum[i + 1][j + k - 1] - sum[i + 1][j - 1]) +
                    (sum[i + 2][j + k - 1] - sum[i + 2][j - 1]);
      long long y = max(seg.query(1, j - k), seg.query(j + k, m - k + 1));
      dp[i + 1][j] = x + y;
      long long L = max(j - k + 1, 1LL), R = min(j + k - 1, m - k + 1);
      dp[i + 1][j] = max(dp[i + 1][j], seg2.query(L, R) + x);
      seg2.add(L, j, a[i + 1][j]);
      seg2.add(j + 1, R, -a[i + 1][j + k]);
      seg2.update(j + k, dp[i][j + k] - a[i + 1][j + k]);
    }
    for (int j = 1; j <= m - k + 1; j++) seg.update(j, dp[i + 1][j]);
  }
  cout << seg.query(1, m - k + 1) << endl;
  return 0;
}

### Prompt

Your challenge is to write a CPP solution to the following problem:

The only difference between easy and hard versions is the constraint on k.

Gildong loves observing animals, so he bought two cameras to take videos of wild animals in a forest. The color of one camera is red, and the other one's color is blue.

Gildong is going to take videos for n days, starting from day 1 to day n. The forest can be divided into m areas, numbered from 1 to m. He'll use the cameras in the following way: 

  * On every odd day (1-st, 3-rd, 5-th, ...), bring the red camera to the forest and record a video for 2 days. 
  * On every even day (2-nd, 4-th, 6-th, ...), bring the blue camera to the forest and record a video for 2 days. 
  * If he starts recording on the n-th day with one of the cameras, the camera records for only one day. 



Each camera can observe k consecutive areas of the forest. For example, if m=5 and k=3, he can put a camera to observe one of these three ranges of areas for two days: [1,3], [2,4], and [3,5].

Gildong got information about how many animals will be seen in each area on each day. Since he would like to observe as many animals as possible, he wants you to find the best way to place the two cameras for n days. Note that if the two cameras are observing the same area on the same day, the animals observed in that area are counted only once.

Input

The first line contains three integers n, m, and k (1 ≤ n ≤ 50, 1 ≤ m ≤ 2 ⋅ 10^4, 1 ≤ k ≤ m) – the number of days Gildong is going to record, the number of areas of the forest, and the range of the cameras, respectively.

Next n lines contain m integers each. The j-th integer in the i+1-st line is the number of animals that can be seen on the i-th day in the j-th area. Each number of animals is between 0 and 1000, inclusive.

Output

Print one integer – the maximum number of animals that can be observed.

Examples

Input


4 5 2
0 2 1 1 0
0 0 3 1 2
1 0 4 3 1
3 3 0 0 4


Output


25


Input


3 3 1
1 2 3
4 5 6
7 8 9


Output


31


Input


3 3 2
1 2 3
4 5 6
7 8 9


Output


44


Input


3 3 3
1 2 3
4 5 6
7 8 9


Output


45

Note

The optimal way to observe animals in the four examples are as follows:

Example 1: 

<image>

Example 2: 

<image>

Example 3: 

<image>

Example 4: 

<image>

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
struct SegTree {
  int size;
  vector<long long> seg;
  SegTree() {}
  SegTree(int size) {
    this->size = size;
    seg.resize(1 << (size + 1));
  }
  void init() {
    for (int i = 0; i < (1 << (size + 1)); i++) seg[i] = -1e18;
  }
  void update(int i, long long val) {
    i += (1 << size);
    seg[i] = val;
    while (i > 1) {
      i /= 2;
      seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
    }
  }
  long long query(int a, int b, int k, int l, int r) {
    if (b < l || r < a) return -1e18;
    if (a <= l && r <= b) return seg[k];
    long long lval = query(a, b, k * 2, l, (l + r) / 2);
    long long rval = query(a, b, k * 2 + 1, (l + r) / 2 + 1, r);
    return max(lval, rval);
  }
  long long query(int a, int b) {
    if (a > b) return -1e18;
    return query(a, b, 1, 0, (1 << size) - 1);
  }
};
struct LazySegTree {
  int size;
  vector<long long> seg, delay;
  LazySegTree() {}
  LazySegTree(int size) {
    this->size = size;
    seg.resize(1 << (size + 1));
    delay.resize(1 << (size + 1));
  }
  void init() {
    for (int i = 0; i < (1 << (size + 1)); i++) {
      seg[i] = -1e18;
      delay[i] = 0;
    }
  }
  void eval(int l, int r, int k) {
    if (delay[k]) {
      seg[k] += delay[k];
      if (l < r) {
        delay[k * 2] += delay[k];
        delay[k * 2 + 1] += delay[k];
      }
      delay[k] = 0;
    }
  }
  void update(int i, long long val) {
    query(i, i);
    i += (1 << size);
    seg[i] = val;
    while (i > 1) {
      i /= 2;
      seg[i] = max(seg[i * 2], seg[i * 2 + 1]);
    }
  }
  void add(int a, int b, int k, int l, int r, long long val) {
    eval(l, r, k);
    if (b < l || r < a) return;
    if (a <= l && r <= b) {
      delay[k] += val;
      eval(l, r, k);
      return;
    }
    add(a, b, k * 2, l, (l + r) / 2, val);
    add(a, b, k * 2 + 1, (l + r) / 2 + 1, r, val);
    seg[k] = max(seg[k * 2], seg[k * 2 + 1]);
  }
  void add(int a, int b, long long val) {
    if (a > b) return;
    add(a, b, 1, 0, (1 << size) - 1, val);
  }
  long long query(int a, int b, int k, int l, int r) {
    eval(l, r, k);
    if (b < l || r < a) return -1e18;
    if (a <= l && r <= b) return seg[k];
    long long lval = query(a, b, k * 2, l, (l + r) / 2);
    long long rval = query(a, b, k * 2 + 1, (l + r) / 2 + 1, r);
    return max(lval, rval);
  }
  long long query(int a, int b) { return query(a, b, 1, 0, (1 << size) - 1); }
};
long long n, m, k;
long long a[55][20005];
long long sum[55][20005];
long long dp[55][20005];
SegTree seg(15);
LazySegTree seg2(15);
int main(void) {
  ios::sync_with_stdio(0);
  cin.tie(0);
  cin >> n >> m >> k;
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m; j++) {
      cin >> a[i][j];
      sum[i][j] = sum[i][j - 1] + a[i][j];
    }
  }
  seg.init();
  for (int i = 1; i <= n; i++) {
    for (int j = 1; j <= m - k + 1; j++) {
      dp[i][j] = -1e18;
    }
  }
  for (int j = 1; j <= m - k + 1; j++) {
    dp[1][j] = (sum[1][j + k - 1] - sum[1][j - 1]) +
               (sum[2][j + k - 1] - sum[2][j - 1]);
    seg.update(j, dp[1][j]);
  }
  seg2.init();
  for (int i = 1; i < n; i++) {
    for (int j = 1; j <= k; j++) {
      seg2.update(j, dp[i][j] - (sum[i + 1][k] - sum[i + 1][j - 1]));
    }
    for (int j = 1; j <= m - k + 1; j++) {
      long long x = (sum[i + 1][j + k - 1] - sum[i + 1][j - 1]) +
                    (sum[i + 2][j + k - 1] - sum[i + 2][j - 1]);
      long long y = max(seg.query(1, j - k), seg.query(j + k, m - k + 1));
      dp[i + 1][j] = x + y;
      long long L = max(j - k + 1, 1LL), R = min(j + k - 1, m - k + 1);
      dp[i + 1][j] = max(dp[i + 1][j], seg2.query(L, R) + x);
      seg2.add(L, j, a[i + 1][j]);
      seg2.add(j + 1, R, -a[i + 1][j + k]);
      seg2.update(j + k, dp[i][j + k] - a[i + 1][j + k]);
    }
    for (int j = 1; j <= m - k + 1; j++) seg.update(j, dp[i + 1][j]);
  }
  cout << seg.query(1, m - k + 1) << endl;
  return 0;
}

```