#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,dbs=0;
for(pair<ll,ll> num:stuffs)
{
num.ff=min(num.ff,x);num.ss=min(num.ss,x);
ll amt=min(num.ff,num.ss);
cno+=amt;
bno+=(num.ss-amt);
rno+=(num.ff-amt);
ll takemore=max(num.ss,num.ff);
if(takemore<x)
{
cno-=min(amt,x-takemore);
dbs+=min(amt,x-takemore);
}
//if(x==2){debu3(num.ff,num.ss,amt);debu2(num.ss-amt,num.ff-amt);}
}
rno=min(rno,ni);bno=min(bno,ni);
ll t1=ni-rno;
t1-=min(t1,dbs);
cno-=t1;
if(cno<0ll)return false;
t1=ni-bno;
t1-=min(t1,dbs);
cno-=t1;
if(cno<0ll)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;
}
