#include "lottery.h"
#include <bits/stdc++.h>
using namespace std;
//#define int long long
#define pb push_back
#define mp make_pair
#define lsb(x) (x&(-x))
#define pii pair<int,int>
#define ss second
#define ff first
#define piii pair<int,pii>
#define debu(x) (cerr << #x << " = "<< x << "\n")
#define debu2(x,y) (cerr << #x << " = "<< x << " " << #y << " = " << y << "\n")
#define debu3(x,y,z) (cerr << #x << " = "<< x << " " << #y << " = " << y << " " << #z << " = " << z<< "\n")
#define bitout(x,y) {\
cerr << #x << " : ";\
for (int justforbits = y; justforbits >=0; justforbits--)cout << (((1 << justforbits) & x)>=1);\
cout << "\n";\
}
#define rangeout(j,rangestart,rangeend) {\
cerr << "outputting " << #j<< ":\n";\
for (int forrang = rangestart; forrang <= rangeend; forrang++)cerr << j[forrang] << " ";\
cerr<<"\n";\
}
#define c1 {cerr << "Checkpoint 1! \n\n";cerr.flush();}
#define c2 {cerr << "Checkpoint 2! \n\n";cerr.flush();}
#define c3 {cerr << "Checkpoint 3! \n\n";cerr.flush();}
#define c4 {cerr << "Checkpoint 4! \n\n";cerr.flush();}
//bin search upper limit too small :(
typedef long long ll;
vector<ll>reds,blues;
bool checkers(ll lsz, ll x, vector<pair<ll,ll>>& stuffs)
{
ll ni=x*lsz;ni/=2;
ll bno=0,rno=0,cno=0;
for(pair<ll,ll>num:stuffs)
{
cno+=min(num.ff+num.ss,x);
rno+=min(num.ff,x);
bno+=min(num.ss,x);
}
rno=min(rno,ni);bno=min(bno,ni);
if(cno<2*ni)return false;
if(bno<ni)return false;
if(rno<ni)return false;
return true;
}
void init(int N, int Q, vector<int> X, vector<int> Y)
{
for(ll x:X)reds.pb(x);
for(ll y:Y)blues.pb(y);
}
int max_prize(int L, int R)
{
ll l=L,r=R;
vector<pair<ll,ll>>stuffs;
for(ll a=l;a<=r;a++)
{
stuffs.pb(mp(reds[a],blues[a]));
}
ll hi=2000000001,lo=0,mid;
while(hi>lo+1ll)
{
mid=(lo+hi)/2ll;
if(checkers(R-L+1,mid,stuffs))
{
lo=mid;
}
else
{
hi=mid;
}
}
return lo;
}
