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
 99
100
101
102
103
104
105
#include <bits/stdc++.h>
#define ll long long
#define pii pair <int,int>
#define ppi pair <pii, int>
#define fi first
#define se second
using namespace std;


template <typename T>
ostream & operator << (ostream &out, const vector <T> &V) {
	if (!V.empty()) {
		out << "{";
		for (auto v : V)
			out << v << ", ";
		out << "\b\b}";			// \b is backspace
	}
	else {
		out << "{}";
	}
	return out;
}

template <class T1, class T2>
ostream & operator << (ostream &out, const pair <T1, T2> &P) {
	out << "{" << P.first << ", " << P.second << "}";
	return out;
}


const int MAX = 300005;
int n, k, q;
ll A[MAX], Pref[MAX];
ll Ans[MAX];
ll D[MAX];



void testcase_qn_at_most_1e7(vector <ppi> &Q) {
	unordered_map <int, vector <pii> > M;
	for (auto &a : Q) {
		M[a.fi.se].push_back({a.fi.fi, a.se});
	}
	for (auto &kv : M) {
		int l = kv.fi; vector <pii> &V = kv.se;
		sort(V.begin(), V.end());
		int r = V[V.size()-1].fi;
		for (int i = l-1; i < l+k-1; i++) {
			D[i] = 0;
		}
		for (int i = l+k-1; i <= r; i++) {
			D[i] = max(D[i-1], D[i-k] + Pref[i] - Pref[i-k]);
		}
		for (pii &a : V) {
			Ans[a.se] = D[a.fi];
		}
	}
}


void testcase_all(vector <ppi> &Q) {
	sort(Q.begin(), Q.end());
	int k1 = k+1;
	vector < vector <ll> > D(k1, vector <ll> (n+1, 0));
	for (int r = 1, q_ind = 0; r <= n && q_ind < q; r++) {
		int row = r % k1, prev_row = (r-1) % k1, prevk1_row = (r-k) % k1;
		for (int i = 1; i <= r; i++) {
			D[row][i] = D[prev_row][i];
			if (i <= r-k+1 && D[row][i] < D[prevk1_row][i-1] + Pref[r] - Pref[r-k]) {
				D[row][i] = D[prevk1_row][i-1] + Pref[r] - Pref[r-k+1];
			}
		}
		while (q_ind < q && Q[q_ind].fi.fi == r) {
			Ans[Q[q_ind].se] = D[row][Q[q_ind].fi.se];
			q_ind++;
		}
	}
}


int main() 
{
	ios_base::sync_with_stdio(false), cin.tie(0), cout.tie(0);
		
	cin >> n >> k >> q;
	
	for (int i = 1; i <= n; i++) {
		cin >> A[i];
		Pref[i] = Pref[i-1] + A[i];
	}
	
	vector <ppi> Q(q);
	for (int i = 0; i < q; i++) {
		cin >> Q[i].fi.se >> Q[i].fi.fi;
		Q[i].se = i;
	}
	
	testcase_qn_at_most_1e7(Q);
	
	for (int i = 0; i < q; i++) {
		cout << Ans[i] <<endl;
	}
	
	return 0;
}