CF1304F2.Animal Observation (hard version)

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.

简单版本与困难版本的唯一区别在于对 $k$ 的约束。

吉隆热衷于观察动物，因此他购买了两台摄像机，用于在森林中拍摄野生动物的视频。其中一台摄像机为红色，另一台为蓝色。

吉隆将连续进行 $n$ 天的拍摄，从第 $1$ 天开始，至第 $n$ 天结束。森林可分为 $m$ 个区域，编号从 $1$ 到 $m$。他将按如下方式使用这两台摄像机：

• 在每个奇数天（第 $1$、$3$、$5$、… 天），携带红色摄像机进入森林，并连续拍摄 $2$ 天；
• 在每个偶数天（第 $2$、$4$、$6$、… 天），携带蓝色摄像机进入森林，并连续拍摄 $2$ 天；
• 若他在第 $n$ 天使用某台摄像机开始拍摄，则该摄像机仅拍摄 $1$ 天。

每台摄像机可同时观测森林中 $k$ 个连续的区域。例如，若 $m=5$ 且 $k=3$，则他可将一台摄像机放置在以下三个区域区间之一，持续观测两天：$[1,3]$、$[2,4]$ 和 $[3,5]$。

吉隆已获知每一天每个区域中将出现的动物数量。由于他希望尽可能多地观测到动物，他请你为这 $n$ 天找出两台摄像机的最佳放置方案。注意：若两台摄像机在同一天观测同一区域，则该区域中出现的动物仅被计数一次。

The first line contains three integers $n$, $m$, and $k$ ($1 \le n \le 50$, $1 \le m \le 2 \cdot 10^4$, $1 \le k \le 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.

第一行包含三个整数 $n$、$m$ 和 $k$（$1 \le n \le 50$，$1 \le m \le 2 \cdot 10^4$，$1 \le k \le m$），分别表示 Gildong 计划记录的天数、森林的区域数量以及摄像头的覆盖范围。

接下来 $n$ 行，每行包含 $m$ 个整数。第 $i+1$ 行中的第 $j$ 个整数表示第 $i$ 天在第 $j$ 个区域中可观测到的动物数量。每个动物数量均在 $0$ 到 $1000$ 之间（含端点）。

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

输出一个整数——能够观察到的动物的最大数量。

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

Example 1:

Example 2:

Example 3:

Example 4:

观察四个示例中动物的最优方式如下：

示例 1：

示例 2：

示例 3：

示例 4：