Kuroni the Private Tutor

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 \le i \le 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 \le n, m \le 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 \le l_{i} \le r_{i} \le m$ ).

The next line contains a single integer $q$ ( $0 \le q \le m$ ).

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

The last line contains a single integer $t$ ( $0 \le t \le 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$ .Examplesinput

output

3 2

input

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.

Solution:

#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...);
}
 
#ifdef LOCAL
#define debug(...) cerr << "[" << #__VA_ARGS__ << "]:", debug_out(__VA_ARGS__)
#else
#define debug(...) 42
#endif
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;
}