#include <bits/stdc++.h>
#define int long long
#define fileopen(a, b) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)b + ".out").c_str(), "w", stdout);
#define fileopen1(a) freopen(((std::string)a + ".inp").c_str(), "r", stdin); freopen(((std::string)a + ".out").c_str(), "w", stdout);
using namespace std;
const int MAXN = 2e5 + 5;
vector<int> group[MAXN];
int l[MAXN], r[MAXN];
int pidx[MAXN];
int pstart[MAXN];
struct state {
int idx, cur, cnt, lst;
bool skippable, is_base;
state() {}
state(int I, int a, int b, int c): idx(I), cur(a), cnt(b), lst(c) {
skippable = is_base = 0;
}
bool operator < (state p) const {
return idx < p.idx;
}
};
int lst(int a) {
return (l[a] ? group[a][l[a] - 1] : 0);
}
signed main() {
#ifndef PICHU_LOCAL_DEF
//fileopen1("LAH");
#endif
cin.tie(0)->sync_with_stdio(0);
int n, m, k;
cin >> n >> m >> k;
for (int i = 1; i <= n; i++) {
int a, c; cin >> a >> c;
group[a].push_back(c);
}
for (int i = 1; i <= m; i++) {
cin >> l[i] >> r[i];
}
priority_queue<pair<int, state>, vector<pair<int, state>>, greater<pair<int, state>>> pq;
int base = 0;
for (int i = 1; i <= m; i++) {
sort(group[i].begin(), group[i].end());
int sz = group[i].size();
if (sz < l[i]) {
while (k--) cout << -1 << '\n';
return 0;
}
for (int j = 0; j < l[i]; j++) base += group[i][j];
pidx[i] = i;
}
sort(pidx + 1, pidx + m + 1, [](int a, int b) {
int left;
if (!r[a]) left = 1e9;
else left = (l[a] == group[a].size() ? 1e9 : group[a][l[a]] - lst(a));
int right;
if (!r[b]) right = 1e9;
else right = (l[b] == group[b].size() ? 1e9 : group[b][l[b]] - lst(b));
return left < right;
});
state sv;
if (l[pidx[1]]) sv = state(1, l[pidx[1]] - 1, 1, group[pidx[1]].size()),
sv.is_base = 1;
else {
sv = state(1, 0, 1, group[pidx[1]].size());
cout << base << '\n';
base += group[pidx[1]][0];
sv.skippable = 1;
sv.is_base = 0;
k--;
}
pq.push({base, sv});
for (int i = 1; i <= k; i++) {
if (pq.empty()) {
cout << -1;
if (i < k) cout << '\n';
continue;
}
else {
auto cs = pq.top(); pq.pop();
int cost = cs.first; state st = cs.second;
cout << cost;
if (i < k) cout << '\n';
// Divide into different states
int idx = pidx[st.idx], nidx = pidx[st.idx + 1];
// Move to next idx
if (!st.is_base && st.idx < m && l[nidx] != group[nidx].size() && r[nidx]) {
state nw(st.idx + 1, l[nidx], 1, group[nidx].size());
nw.skippable = 1;
if (st.skippable) {
pq.push({cost + group[nidx][l[nidx]] - lst(nidx) - group[idx][l[idx]] + lst(idx), nw});
}
pq.push({cost + group[nidx][l[nidx]] - lst(nidx), nw});
}
// move cur to right
if (st.cur + 1 < st.lst) {
state nw = st;
nw.is_base = nw.skippable = 0;
if (st.is_base) {
nw.is_base = 0;
nw.skippable = 1;
}
nw.cur++;
pq.push({cost + group[idx][nw.cur] - group[idx][nw.cur - 1], nw});
}
// fix cur, move pointer before
{
state nw = st;
nw.lst = st.cur;
nw.is_base = nw.skippable = 0;
if (st.cnt < l[idx]) {
nw.cnt++;
int nxt = l[idx] - st.cnt - 1;
nw.cur = nxt + 1;
if (nw.cur < nw.lst) pq.push({cost - group[idx][nxt] + group[idx][nxt + 1], nw});
}
}
// add new pointer to 0
if (st.cnt >= l[idx] && st.cnt < r[idx]) {
state nw = st;
nw.is_base = nw.skippable = 0;
nw.cnt++;
nw.lst = st.cur;
nw.cur = 0;
if (nw.lst) pq.push({cost + group[idx][0], nw});
}
}
}
}
