1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
#include <iostream>
#include <set>
#include <vector>
#include <algorithm>
#include <cstring>
#include <cmath>
#include <list>

using namespace std;
#undef _HOME_
#ifdef _HOME_
    #define DEBUG(x) x
#else
    #define DEBUG(x)
#endif
#define REP(x,n) for(int x=0;x<(n);++x)
#define FOREACH(x,n) for(__typeof(n.begin()) x = (n).begin(); x != (n).end(); ++x)
#define RESULT(x) {cout<<(x);return 0;}

const long long INF = 1000000000000000000LL; // 1e18
const int MAX_N = 300001;
int tab[MAX_N];
long long sumPref[MAX_N];
int n,k,q;
int l,r;

template<typename _T> struct Heap {
	vector<_T> elems;
	void add(_T& elem) {
		elems.push_back(elem);
		push_heap(elems.begin(), elems.end());
	}
	_T removeTop() {
		pop_heap(elems.begin(), elems.end());
		elems.pop_back();
	}
	const _T& top() {
		return elems[0];
	}
};

long long groups[MAX_N];
long long maxTab[MAX_N];

long long solve(int l, int r) {
	int end = r-k+1;
	DEBUG(cerr<<"solve "<<l<<", "<<end<<endl;)
	if (end < l)
		return 0;
	if (end == l)
		return groups[l];
	maxTab[l] = groups[l];
	for(int x=l+1; x<l+k; ++x) {
		maxTab[x] = max(maxTab[x-1], groups[x]);
		DEBUG(cerr<<"maxTab1["<<x<<"] = max("<<maxTab[x-1]<<", "<<groups[x]<<") = "<<maxTab[x]<<endl;)
	}
	for(int x=l+k;x<=end;++x) {
		maxTab[x] = max(maxTab[x-1], maxTab[x-k]+groups[x]);
		DEBUG(cerr<<"maxTab2["<<x<<"] = max("<<maxTab[x-1]<<", "<<maxTab[x-k]<<"+"<<groups[x]<<") = "<<maxTab[x]<<endl;)
	}
	return maxTab[end];
}

int main() {
	ios_base::sync_with_stdio(0);
	cin>>n>>k>>q;
	int groupsCnt = n-k+1;
	long long sum=0LL;
	REP(x,n) {
		cin>>tab[x];
		sumPref[x+1] = (sum+=tab[x]);
	}
	sum=0;
	REP(x,k)
		sum += tab[x];
	REP(x,groupsCnt) {
		groups[x] = max(sum, 0LL);
		sum += tab[x+k] - tab[x];
	}

	DEBUG(
		cerr<<"groups"<<endl;
		REP(x,n)
			cerr<<groups[x]<<" ";
		cerr<<endl;
	)
	REP(x,q) {
		cin>>l>>r;
		cout << solve(l-1,r-1) << endl;
	}
	return 0;
}