#include <bits/stdc++.h>
#define ll long long
#define mid ((l + r) >> 1)
#define lowbit(x) (x & -x)
using namespace std;
constexpr int N = 2e5 + 5;
int n, m, k;
int l[N], r[N], ord[N];
vector<int> a[N];
struct Node1 {
int x, y, z;
ll w;
bool operator<(const Node1& t) const {
return w > t.w;
}
};
struct Node2 {
int x, y;
ll w;
bool operator<(const Node2& t) const {
return w > t.w;
}
};
priority_queue<Node1> q[N];
vector<ll> res[N];
ll get(int i, int k) {
if (res[i].size() >= k) {
return res[i][k - 1];
}
if (res[i].size() == 0) {
ll cnt = 0;
for (int j = 0; j < l[i]; ++j) {
cnt += a[i][j];
}
q[i].push({l[i] - 1, l[i] - 1, a[i].size(), cnt});
}
while (res[i].size() < k && !q[i].empty()) {
auto u = q[i].top();
q[i].pop();
res[i].push_back(u.w);
if (u.x == u.y && u.y + 1 < min(u.z, r[i]) && u.z == a[i].size()) {
q[i].push({u.x + 1, u.x + 1, u.z, u.w + a[i][u.x + 1]});
}
if (u.x >= 0) {
if (u.y + 1 < u.z) {
q[i].push({u.x, u.y + 1, u.z, u.w + (a[i][u.y + 1] - a[i][u.y])});
}
if (u.x < u.y && u.x > 0) {
q[i].push({u.x - 1, u.x, u.y, u.w + (a[i][u.x] - a[i][u.x - 1])});
}
}
}
if (res[i].size() < k) {
return -1;
} else {
return res[i][k - 1];
}
}
signed main() {
ios::sync_with_stdio(false);
cin.tie(nullptr); cout.tie(nullptr);
cin >> n >> m >> k;
for (int i = 1; i <= n; ++i) {
int x, y;
cin >> x >> y;
a[x].push_back(y);
}
for (int i = 1; i <= m; ++i) {
cin >> l[i] >> r[i];
if (a[i].size() < l[i]) {
for (int j = 1; j <= k; ++j) {
cout << "-1\n";
}
return 0;
}
sort(a[i].begin(), a[i].end());
}
iota(ord + 1, ord + m + 1, 1);
sort(ord + 1, ord + m + 1, [](int x, int y) {
if (get(x, 2) < 0 || get(y, 2) < 0) {
return get(x, 2) > get(y, 2);
}
return get(x, 2) - get(x, 1) < get(y, 2) - get(y, 1);
});
ll w = 0;
for (int i = 1; i <= m; ++i) {
w += get(i, 1);
}
cout << w << '\n';
priority_queue<Node2> q;
if (get(ord[1], 2) >= get(ord[1], 1)) {
q.push({1, 2, w + (get(ord[1], 2) - get(ord[1], 1))});
}
for (int i = 1; i < k; ++i) {
if (q.empty()) {
cout << "-1\n";
continue;
}
auto u = q.top();
q.pop();
cout << u.w << '\n';
w = get(ord[u.x], u.y + 1) - get(ord[u.x], u.y);
if (w >= 0) {
q.push({u.x, u.y + 1, u.w + w});
}
if (u.x < m) {
w = get(ord[u.x + 1], 2) - get(ord[u.x + 1], 1);
if (w >= 0) {
q.push({u.x + 1, 2, u.w + w});
if (u.y == 2) {
w = (get(ord[u.x + 1], 2) - get(ord[u.x + 1], 1)) - (get(ord[u.x], 2) - get(ord[u.x], 1));
if (w >= 0) {
q.push({u.x + 1, 2, u.w + w});
}
}
}
}
}
return 0;
}
