#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) {
// for (ll d = 0; d < i; d++) cout << "\t";
// cout << numRed << endl;
ll ind = L + i;
if (ind == R + 1) return true;
if (memo[i][numRed] != -1) {
return memo[i][numRed];
}
bool isPossible = false;
for (ll nRed = 0; nRed <= X[ind]; nRed++) {
if (numRed < nRed) 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;
// ll res = 0;
// for (ll numWinners = 0; numWinners <= 200; numWinners++) {
// numWinner = numWinners;
// memo.clear();
// memo.resize(100, vector<int>(10001, -1));
// // cout << "numWinners: " << numWinners << endl;
// if (dp(0, numWinners * ((R - L + 1) / 2))) {
// res = numWinners;
// } else {
// break;
// }
// }
// return res;
ll l = 0, r = 1000;
// max TRUE
while (l < r) {
ll numWinners = l + (r - l + 1) / 2;
numWinner = numWinners;
memo.assign(100, vector<int>(10001, -1));
if (dp(0, numWinners * ((R - L + 1) / 2))) {
l = numWinners;
} else {
r = numWinners - 1;
}
}
return l;
}
