#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
#define popcount __builtin_popcount
#define all(a) (a).begin(), (a).end()
using namespace std;
using namespace chrono;
using namespace __gnu_pbds;
template<typename T> using ordered_set = tree<T,null_type,less_equal<>,rb_tree_tag,tree_order_statistics_node_update>;
vector<int> X, Y;
void init(int N, int Q, std::vector<int> _X, std::vector<int> _Y) {
X = _X;
Y = _Y;
}
bool check(int l, int r, int k) {
long long mn = 0, mx = 0;
for (int i = l; i < r; i++) {
if (X[i] + Y[i] < k) return false;
mn += max(0, k - Y[i]);
mx += min(X[i], k);
}
long long half = (r-l)/2 * k;
// cout<<l<<' '<<r<<' '<<k<<": "<<mn<<' '<<half<<' '<<mx<<'\n';
return mn <= half && half <= mx;
}
int max_prize(int l, int r) {
r++;
long long lo = 0, hi = 2e9+1;
while (lo+1 < hi) {
auto mid = (lo + hi)/2;
(check(l, r, mid) ? lo : hi) = mid;
}
return lo;
}
