#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> L(n), R(n);
  for (int i = 0; i < n; i++) {
    cin >> L[i] >> R[i];
  }
  vector<int> val(m, -1);
  int tt;
  cin >> tt;
  while (tt--) {
    int x, y;
    cin >> x >> y;
    --x;
    val[x] = y;
  }
  long long t;
  cin >> t;
  long long sL = 0, sR = 0;
  for (int i = 0; i < n; i++) {
    sL += L[i];
    sR += R[i];
  }
  if (t < sL || t > sR) {
    cout << "-1 -1" << '\n';
    return 0;
  }
  vector<vector<int>> at(m + 1);
  for (int i = 0; i < n; i++) {
    at[L[i]].push_back(i);
  }
  long long cur = sL;
  set<pair<int, int>> s;
  for (int i = 0; i <= m; i++) {
    for (int j : at[i]) {
      s.emplace(R[j], j);
    }
    while (!s.empty() && s.begin()->first == i) {
      L[s.begin()->second] = i;
      s.erase(s.begin());
    }
    while ((long long)s.size() > t - cur) {
      L[s.begin()->second] = i;
      s.erase(s.begin());
    }
    cur += (long long)s.size();
  }
  assert(cur == t);
  assert(s.empty());
  vector<long long> maxp(m);
  for (int x : L) {
    maxp[0] += 1;
    if (x < m) {
      maxp[x] -= 1;
    }
  }
  long long aux = 0;
  long long delta = 0;
  for (int i = 0; i < m; i++) {
    delta += maxp[i];
    aux += delta;
    maxp[i] = aux;
  }
  vector<int> a = val;
  auto Test = [&]() {
    for (int i = 0; i < m - 1; i++) {
      if (a[i] != -1 && a[i + 1] != -1 && a[i] < a[i + 1]) {
        return false;
      }
    }
    vector<tuple<int, int, int, int>> segs;
    {
      int beg = 0;
      cur = 0;
      while (beg < m) {
        if (a[beg] != -1) {
          cur += a[beg];
          ++beg;
          continue;
        }
        int end = beg;
        while (end + 1 < m && a[end + 1] == -1) {
          ++end;
        }
        int low = (end == m - 1 ? 0 : a[end + 1]);
        int high = (beg == 0 ? n : a[beg - 1]);
        if (low > high) {
          return false;
        }
        cur += (long long)low * (end - beg + 1);
        segs.emplace_back(beg, end, low, high);
        beg = end + 1;
      }
    }
    if (cur > t) {
      return false;
    }
    for (int it = (int)segs.size() - 1; it >= 0; it--) {
      auto& seg = segs[it];
      int beg = get<0>(seg);
      int end = get<1>(seg);
      int low = get<2>(seg);
      int high = get<3>(seg);
      long long add = (long long)(end - beg + 1) * (high - low);
      if (cur + add <= t) {
        for (int i = beg; i <= end; i++) {
          a[i] = high;
        }
        cur += add;
      } else {
        long long to_all = (t - cur) / (end - beg + 1);
        for (int i = beg; i <= end; i++) {
          a[i] = (int)(low + to_all);
        }
        cur += to_all * (end - beg + 1);
        for (int i = beg; i < beg + (t - cur); i++) {
          a[i] += 1;
        }
        cur = t;
      }
    }
    if (cur != t) {
      return false;
    }
    aux = 0;
    for (int i = 0; i < m; i++) {
      aux += a[i];
      if (aux > maxp[i]) {
        return false;
      }
    }
    return true;
  };
  if (!Test()) {
    cout << "-1 -1" << '\n';
    return 0;
  }
  int first = a[0];
  int low = 1, high = m;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    a = val;
    if (a[mid - 1] != -1 && a[mid - 1] != first) {
      high = mid - 1;
      continue;
    }
    a[mid - 1] = first;
    if (Test()) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  int people = low;
  low = first, high = n;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    a = val;
    if (a[people - 1] != -1 && a[people - 1] != mid) {
      high = mid - 1;
      continue;
    }
    a[people - 1] = mid;
    if (Test()) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  int score = low;
  cout << people << " " << score << '\n';
  return 0;
}

### Prompt

Please formulate a cpp solution to the following problem:

As a professional private tutor, Kuroni has to gather statistics of an exam. Kuroni has appointed you to complete this important task. You must not disappoint him.

The exam consists of n questions, and m students have taken the exam. Each question was worth 1 point. Question i was solved by at least l_i and at most r_i students. Additionally, you know that the total score of all students is t.

Furthermore, you took a glance at the final ranklist of the quiz. The students were ranked from 1 to m, where rank 1 has the highest score and rank m has the lowest score. Ties were broken arbitrarily.

You know that the student at rank p_i had a score of s_i for 1 ≤ i ≤ q.

You wonder if there could have been a huge tie for first place. Help Kuroni determine the maximum number of students who could have gotten as many points as the student with rank 1, and the maximum possible score for rank 1 achieving this maximum number of students.

Input

The first line of input contains two integers (1 ≤ n, m ≤ 10^{5}), denoting the number of questions of the exam and the number of students respectively.

The next n lines contain two integers each, with the i-th line containing l_{i} and r_{i} (0 ≤ l_{i} ≤ r_{i} ≤ m).

The next line contains a single integer q (0 ≤ q ≤ m). 

The next q lines contain two integers each, denoting p_{i} and s_{i} (1 ≤ p_{i} ≤ m, 0 ≤ s_{i} ≤ n). It is guaranteed that all p_{i} are distinct and if p_{i} ≤ p_{j}, then s_{i} ≥ s_{j}.

The last line contains a single integer t (0 ≤ t ≤ nm), denoting the total score of all students.

Output

Output two integers: the maximum number of students who could have gotten as many points as the student with rank 1, and the maximum possible score for rank 1 achieving this maximum number of students. If there is no valid arrangement that fits the given data, output -1 -1.

Examples

Input


5 4
2 4
2 3
1 1
0 1
0 0
1
4 1
7


Output


3 2


Input


5 6
0 6
0 6
2 5
6 6
4 6
1
3 3
30


Output


-1 -1

Note

For the first sample, here is one possible arrangement that fits the data:

Students 1 and 2 both solved problems 1 and 2.

Student 3 solved problems 2 and 3.

Student 4 solved problem 4.

The total score of all students is T = 7. Note that the scores of the students are 2, 2, 2 and 1 respectively, which satisfies the condition that the student at rank 4 gets exactly 1 point. Finally, 3 students tied for first with a maximum score of 2, and it can be proven that we cannot do better with any other arrangement.

### Response

```cpp
#include <bits/stdc++.h>
using namespace std;
template <typename A, typename B>
string to_string(pair<A, B> p);
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p);
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p);
string to_string(const string& s) { return '"' + s + '"'; }
string to_string(const char* s) { return to_string((string)s); }
string to_string(bool b) { return (b ? "true" : "false"); }
string to_string(vector<bool> v) {
  bool first = true;
  string res = "{";
  for (int i = 0; i < static_cast<int>(v.size()); i++) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(v[i]);
  }
  res += "}";
  return res;
}
template <size_t N>
string to_string(bitset<N> v) {
  string res = "";
  for (size_t i = 0; i < N; i++) {
    res += static_cast<char>('0' + v[i]);
  }
  return res;
}
template <typename A>
string to_string(A v) {
  bool first = true;
  string res = "{";
  for (const auto& x : v) {
    if (!first) {
      res += ", ";
    }
    first = false;
    res += to_string(x);
  }
  res += "}";
  return res;
}
template <typename A, typename B>
string to_string(pair<A, B> p) {
  return "(" + to_string(p.first) + ", " + to_string(p.second) + ")";
}
template <typename A, typename B, typename C>
string to_string(tuple<A, B, C> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ")";
}
template <typename A, typename B, typename C, typename D>
string to_string(tuple<A, B, C, D> p) {
  return "(" + to_string(get<0>(p)) + ", " + to_string(get<1>(p)) + ", " +
         to_string(get<2>(p)) + ", " + to_string(get<3>(p)) + ")";
}
void debug_out() { cerr << endl; }
template <typename Head, typename... Tail>
void debug_out(Head H, Tail... T) {
  cerr << " " << to_string(H);
  debug_out(T...);
}
int main() {
  ios::sync_with_stdio(false);
  cin.tie(0);
  int n, m;
  cin >> n >> m;
  vector<int> L(n), R(n);
  for (int i = 0; i < n; i++) {
    cin >> L[i] >> R[i];
  }
  vector<int> val(m, -1);
  int tt;
  cin >> tt;
  while (tt--) {
    int x, y;
    cin >> x >> y;
    --x;
    val[x] = y;
  }
  long long t;
  cin >> t;
  long long sL = 0, sR = 0;
  for (int i = 0; i < n; i++) {
    sL += L[i];
    sR += R[i];
  }
  if (t < sL || t > sR) {
    cout << "-1 -1" << '\n';
    return 0;
  }
  vector<vector<int>> at(m + 1);
  for (int i = 0; i < n; i++) {
    at[L[i]].push_back(i);
  }
  long long cur = sL;
  set<pair<int, int>> s;
  for (int i = 0; i <= m; i++) {
    for (int j : at[i]) {
      s.emplace(R[j], j);
    }
    while (!s.empty() && s.begin()->first == i) {
      L[s.begin()->second] = i;
      s.erase(s.begin());
    }
    while ((long long)s.size() > t - cur) {
      L[s.begin()->second] = i;
      s.erase(s.begin());
    }
    cur += (long long)s.size();
  }
  assert(cur == t);
  assert(s.empty());
  vector<long long> maxp(m);
  for (int x : L) {
    maxp[0] += 1;
    if (x < m) {
      maxp[x] -= 1;
    }
  }
  long long aux = 0;
  long long delta = 0;
  for (int i = 0; i < m; i++) {
    delta += maxp[i];
    aux += delta;
    maxp[i] = aux;
  }
  vector<int> a = val;
  auto Test = [&]() {
    for (int i = 0; i < m - 1; i++) {
      if (a[i] != -1 && a[i + 1] != -1 && a[i] < a[i + 1]) {
        return false;
      }
    }
    vector<tuple<int, int, int, int>> segs;
    {
      int beg = 0;
      cur = 0;
      while (beg < m) {
        if (a[beg] != -1) {
          cur += a[beg];
          ++beg;
          continue;
        }
        int end = beg;
        while (end + 1 < m && a[end + 1] == -1) {
          ++end;
        }
        int low = (end == m - 1 ? 0 : a[end + 1]);
        int high = (beg == 0 ? n : a[beg - 1]);
        if (low > high) {
          return false;
        }
        cur += (long long)low * (end - beg + 1);
        segs.emplace_back(beg, end, low, high);
        beg = end + 1;
      }
    }
    if (cur > t) {
      return false;
    }
    for (int it = (int)segs.size() - 1; it >= 0; it--) {
      auto& seg = segs[it];
      int beg = get<0>(seg);
      int end = get<1>(seg);
      int low = get<2>(seg);
      int high = get<3>(seg);
      long long add = (long long)(end - beg + 1) * (high - low);
      if (cur + add <= t) {
        for (int i = beg; i <= end; i++) {
          a[i] = high;
        }
        cur += add;
      } else {
        long long to_all = (t - cur) / (end - beg + 1);
        for (int i = beg; i <= end; i++) {
          a[i] = (int)(low + to_all);
        }
        cur += to_all * (end - beg + 1);
        for (int i = beg; i < beg + (t - cur); i++) {
          a[i] += 1;
        }
        cur = t;
      }
    }
    if (cur != t) {
      return false;
    }
    aux = 0;
    for (int i = 0; i < m; i++) {
      aux += a[i];
      if (aux > maxp[i]) {
        return false;
      }
    }
    return true;
  };
  if (!Test()) {
    cout << "-1 -1" << '\n';
    return 0;
  }
  int first = a[0];
  int low = 1, high = m;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    a = val;
    if (a[mid - 1] != -1 && a[mid - 1] != first) {
      high = mid - 1;
      continue;
    }
    a[mid - 1] = first;
    if (Test()) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  int people = low;
  low = first, high = n;
  while (low < high) {
    int mid = (low + high + 1) >> 1;
    a = val;
    if (a[people - 1] != -1 && a[people - 1] != mid) {
      high = mid - 1;
      continue;
    }
    a[people - 1] = mid;
    if (Test()) {
      low = mid;
    } else {
      high = mid - 1;
    }
  }
  int score = low;
  cout << people << " " << score << '\n';
  return 0;
}

```