1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
#include<iostream>
#include<cstdlib>
#include<cstdio>
using namespace std;
long long n,k,q,t[300005],t2[300005],tab[300005],a,b;
int main(){
  scanf("%lld%lld%lld",&n,&k,&q);
  for(int i=1;i<=n;i++) scanf("%lld",&t[i]);
  t2[k]=t[k];
  for(int i=1;i<k;i++) t2[i]=0,t2[k]+=t[i];
  for(int i=k+1;i<=n;i++) t2[i]=t2[i-1]+t[i]-t[i-k];
  for(int i=0;i<q;i++){
    scanf("%lld%lld",&a,&b);
    for(int u=a-1;u<a+k-1;u++) tab[u]=0;
    for(int u=a+k-1;u<=b;u++)
      tab[u]=max(tab[u-k]+t2[u],tab[u-1]);
    printf("%lld\n",tab[b]);
  }
  return 0;
}