#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 = 200;
// // max TRUE
// while (l < r) {
// ll numWinners = l + (r - l + 1) / 2;
// numWinner = numWinners;
// memo.clear();
// memo.resize(N, vector<int>(10001));
// if (dp(0, numWinners * (N / 2))) {
// r = numWinners;
// } else {
// l = numWinners + 1;
// }
// }
// return l;
}
