#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
using ll = int;
int N;
vector<int> X;
vector<int> Y;
int L, R;
int numWinner;
vector<vector<int> > memo;
bool dp(ll i, ll numRed) {
ll ind = L + i;
if (ind == R + 1) {
return (numRed == 0);
}
if (memo[i][numRed] != -1) {
return memo[i][numRed];
}
bool isPossible = false;
for (ll nRed = 0; nRed <= X[ind]; nRed++) {
if (nRed > numRed || nRed > numWinner) break;
if (nRed + Y[ind] >= numWinner) {
isPossible = isPossible || dp(i + 1, numRed - nRed);
}
}
return memo[i][numRed] = isPossible;
}
void init(int n, int Q, vector<int> x, vector<int> y) {
N = n;
X = x, Y = y;
}
int max_prize(int lInd, int rInd) {
L = lInd, R = rInd;
// max TRUE
ll l = 0, r = 500;
while (l < r) {
ll numWinners = l + (r - l + 1) / 2;
numWinner = numWinners;
memo.clear();
memo.assign(R - L + 4, vector<int>(numWinners * ((R - L + 1) / 2) + 1, -1));
if (dp(0, numWinners * ((R - L + 1) / 2))) {
l = numWinners;
} else {
r = numWinners - 1;
}
}
return l;
}
