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
93
94
95
96
97
98
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=3e5+7;
ll ans[LIM], T[LIM], n, k, q;
void dc(int l, int r, vector<pair<pair<int,int>,int>>&V) {
	if(l==r) {
		if(T[l]>0) for(auto i : V) ans[i.nd]=T[l];
		return;
	}
	int mid=(l+r)/2;
	ll dpl[mid-l+1][k], dpr[r-mid][k];
	rep(i, mid-l+1) rep(j, k) dpl[i][j]=0;
	rep(i, k) {
		ll ma1=0, ma2=0;
		for(int j=mid-i; j>=l; --j) {
			dpl[mid-j][i]=max(ma1, ma2+T[j]);
			ma1=max(ma1, dpl[mid-j][i]);
			if(mid-j-k+1>=0) ma2=max(ma2, dpl[mid-j-k+1][i]);
		}
	}
	rep(i, r-mid) rep(j, k) dpr[i][j]=0;
	rep(i, k) {
		ll ma1=0, ma2=0;
		for(int j=mid+1+i; j<=r; ++j) {
			dpr[j-mid-1][i]=max(ma1, ma2+T[j]);
			ma1=max(ma1, dpr[j-mid-1][i]);
			if(j-mid-k>=0) ma2=max(ma2, dpr[j-mid-k][i]);
		}
	}
	vector<pair<pair<int,int>,int>>lewo, prawo;
	for(auto i : V) {
		if(i.st.st<=mid && mid<i.st.nd) {
			ll ma=0;
			rep(j, k) {
				ma=max(ma, dpr[i.st.nd-mid-1][k-j-1]);
				ans[i.nd]=max(ans[i.nd], dpl[mid-i.st.st][j]+ma);
			}
		} else if(i.st.nd<=mid) lewo.pb(i);
		else prawo.pb(i);
	}
	dc(l, mid, lewo);
	dc(mid+1, r, prawo);
}
void malek() {
	vector<pair<pair<int,int>,int>>V;
	rep(i, q) {
		int a, b;
		cin >> a >> b; --a; --b;
		b-=k-1;
		if(a<=b) V.pb({{a, b}, i});
	}
	dc(0, n-1, V);
}
void brutnq() {
	vector<pair<int,int>>pyt[n];
	rep(i, q) {
		int a, b;
		cin >> a >> b; --a; --b;
		b-=k-1;
		if(a<=b) pyt[a].pb({b, i});
	}
	ll dp[n];
	rep(i, n) {
		if(!pyt[i].size()) continue;
		int ma=0;
		for(auto j : pyt[i]) ma=max(ma, j.st);
		ll ma1=0, ma2=0;
		rep(j, ma-i+1) {
			dp[j]=max(ma1, ma2+T[j+i]);
			ma1=max(ma1, dp[j]);
			if(j-k+1>=0) ma2=max(ma2, dp[j-k+1]);
		}
		for(auto j : pyt[i]) ans[j.nd]=dp[j.st-i];
	}
}
int main() {
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> n >> k >> q;
	rep(i, n) cin >> T[i];
	ll sum=0;
	rep(i, k) sum+=T[i];
	rep(i, n-k+1) {
		sum-=T[i];
		T[i]+=sum;
		sum+=T[i+k];
	}
	n=n-k+1;
	if(k<=500) malek();
	else brutnq();
	rep(i, q) cout << ans[i] << '\n';
}