#include <bits/stdc++.h>
using namespace std;
const int64_t INF = 1E18;
struct sorted_subsets {
vector<int64_t> a, ans;
int l, r;
using node = tuple<int64_t, int, int, int>;
priority_queue<node, vector<node>, greater<node>> pq;
sorted_subsets(vector<int64_t> a_, int l_, int r_) : l(l_), r(r_) {
a = a_;
sort(a.begin(), a.end());
if (l == 0) {
pq.push({0, -1, -1, -1});
}
int64_t val = 0;
for (int i = 0; i < a.size(); i++) {
val += a[i];
if (i + 1 >= l && i + 1 <= r) {
pq.push({val, i, i, a.size()});
}
}
}
int64_t operator[](int i) {
while (i >= ans.size()) {
if (pq.empty()) {
break;
}
auto [v, c, i, h] = pq.top(); pq.pop();
ans.push_back(v);
if (c == -1) {
continue;
}
if (i + 1 < h) {
pq.push({v - a[i] + a[i + 1], c, i + 1, h});
}
if (c > 0 && c < i) {
pq.push({v - a[c - 1] + a[c], c - 1, c, i});
}
}
return i < ans.size() ? ans[i] : INF;
}
};
void solve() {
int n, m, k; cin >> n >> m >> k;
vector<vector<int64_t>> a(m);
for (int i = 0; i < n; i++) {
int u, t; cin >> t >> u; t--;
a[t].push_back(u);
}
vector<sorted_subsets> all;
for (int i = 0; i < m; i++) {
int l, r; cin >> l >> r;
all.push_back(sorted_subsets(a[i], l, r));
}
sort(all.begin(), all.end(), [&](auto& u, auto& v) {
return u[1] - u[0] < v[1] - v[0];
});
// value, current index, current pos
using node = tuple<int64_t, int, int>;
priority_queue<node, vector<node>, greater<node>> pq;
{
// make init node
int64_t val = 0;
for (int i = 0; i < m; i++) {
val += all[i][0];
if (all[i][0] == INF) {
val = INF;
}
}
pq.push({val, -1, 0});
}
for (int it = 0; it < k; it++) {
if (pq.empty()) {
cout << "-1\n"; continue;
}
auto [v, i, p] = pq.top(); pq.pop();
if (v >= INF) {
cout << "-1\n"; continue;
}
cout << v << '\n';
// add 1 to current index
if (i != -1) {
pq.push({v + all[i][p + 1] - all[i][p], i, p + 1});
}
// push 1 to next index
if (i + 1 < m) {
pq.push({v + all[i + 1][1] - all[i + 1][0], i + 1, 1});
}
// remove 1 from current and push 1 to next index (only applicable when p = 1)
if (p == 1 && i + 1 < m) {
pq.push({v + all[i + 1][1] - all[i + 1][0] + all[i][0] - all[i][1], i + 1, 1});
}
}
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(nullptr);
int t = 1; // cin >> t;
while (t--) {
solve();
}
}
