#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
int N;
vector<int> X;
vector<int> Y;
bool dp(ll L, ll R, ll numWinner) {
vector<pair<ll, ll> > pairs(R - L + 1);
for (int i = L; i <= R; i++) {
pairs[i - L] = {X[i], Y[i]};
}
sort(pairs.begin(), pairs.end());
reverse(pairs.begin(), pairs.end());
ll numRed = numWinner * (R - L + 1)/2;
ll numBlue = numWinner * (R - L + 1)/2;
for (ll i = 0; i < pairs.size(); i++) {
if (pairs[i].first < numWinner - pairs[i].second) return false;
if (pairs[i].second < numWinner - pairs[i].first) return false;
numRed -= min({pairs[i].first, numWinner, numRed});
numBlue -= min({pairs[i].second, numWinner, numBlue});
}
return (numRed == 0) && (numBlue == 0);
}
void init(int n, int Q, vector<int> x, vector<int> y) {
N = n;
X = x, Y = y;
}
int max_prize(int L, int R) {
// max TRUE
ll l = 0, r = 500;
while (l < r) {
ll numWinners = l + (r - l + 1) / 2;
if (dp(L, R, numWinners)) {
l = numWinners;
} else {
r = numWinners - 1;
}
}
return l;
}
