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
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.
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; }