#include <iostream>
#include <sstream>
#include <iomanip>
#include <vector>
#include <string>
#include <map>
#include <set>
#include <algorithm>
#include <numeric>
#include <iterator>
#include <functional>
#include <complex>
#include <queue>
#include <stack>
#include <cmath>
#include <cassert>
#include <tuple>
using namespace std;
typedef long long LL;
typedef complex<double> CMP;
class EllysPairing { public:
int getMax(int M, vector <int> count, vector <int> first, vector <int> mult, vector <int> add)
{
int all = accumulate(count.begin(), count.end(), 0);
int max_cnt = maxFreq(M, 0, M, count, first, mult, add);
if(max_cnt <= all/2)
return all/2;
else
return all - max_cnt;
}
int maxFreq(unsigned M, int L, int R,
const vector<int>& count, const vector<int>& first, const vector<int>& mult, const vector<int>& add)
{
static const int Z = 1<<20;
if(R-L <= Z) {
int freq[Z] = {};
for(int i=0; i<count.size(); ++i) {
unsigned c = count[i];
unsigned f = first[i];
unsigned m = mult[i];
unsigned a = add[i];
for(unsigned k=0; k<c; ++k) {
if(L<=f && f<R) freq[f-L]++;
f=(f*m+a)&(M-1);
}
}
return *max_element(freq, freq+(R-L));
}
int freq[2] = {}, C = L+(R-L)/2;
for(int i=0; i<count.size(); ++i) {
unsigned c = count[i];
unsigned f = first[i];
unsigned m = mult[i];
unsigned a = add[i];
for(unsigned k=0; k<c; ++k) {
if(L<=f && f<R)
freq[f<C ? 0 : 1]++;
f=(f*m+a)&(M-1);
}
}
if(freq[0] < freq[1])
return maxFreq(M, C, R, count, first, mult, add);
else
return maxFreq(M, L, C, count, first, mult, add);
}
};
// BEGIN CUT HERE
#include <ctime>
double start_time; string timer()
{ ostringstream os; os << " (" << int((clock()-start_time)/CLOCKS_PER_SEC*1000) << " msec)"; return os.str(); }
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{ os << "{ ";
for(typename vector<T>::const_iterator it=v.begin(); it!=v.end(); ++it)
os << '\"' << *it << '\"' << (it+1==v.end() ? "" : ", "); os << " }"; return os; }
void verify_case(const int& Expected, const int& Received) {
bool ok = (Expected == Received);
if(ok) cerr << "PASSED" << timer() << endl; else { cerr << "FAILED" << timer() << endl;
cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl; } }
#define CASE(N) {cerr << "Test Case #" << N << "..." << flush; start_time=clock();
#define END verify_case(_, EllysPairing().getMax(M, count, first, mult, add));}
int main(){
CASE(0)
int M = 16;
int count_[] = {4, 7};
vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
int first_[] = {5, 3};
vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
int mult_[] = {2, 3};
vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
int add_[] = {1, 0};
vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
int _ = 5;
END
CASE(1)
int M = 8;
int count_[] = {6, 4, 3};
vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
int first_[] = {0, 3, 2};
vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
int mult_[] = {3, 7, 5};
vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
int add_[] = {0, 3, 2};
vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
int _ = 5;
END
CASE(2)
int M = 128;
int count_[] = {42, 13, 666, 17, 1337, 42, 1};
vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
int first_[] = {18, 76, 3, 122, 0, 11, 11};
vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
int mult_[] = {33, 17, 54, 90, 41, 122, 20};
vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
int add_[] = {66, 15, 10, 121, 122, 1, 30};
vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
int _ = 1059;
END
CASE(3)
int M = 1048576;
int count_[] = {4242, 42, 9872, 13, 666, 21983, 17, 1337, 42, 1};
vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
int first_[] = {19, 18, 76, 42, 3, 112, 0, 11, 11, 12};
vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
int mult_[] = {27, 33, 10, 8, 17, 9362, 90, 41, 122, 20};
vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
int add_[] = {98, 101, 66, 15, 10, 144, 3, 1, 5, 1};
vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
int _ = 16232;
END
CASE(4)
int M = 1073741824;
int count_[] = {894602, 946569, 887230, 856152, 962583, 949356, 904847, 829100, 842183, 958440,
811081, 864078, 809209, 938727, 949135, 892809, 816528, 961237, 979142, 890922};
vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
int first_[] = {844085078, 898937259, 243490172, 887804102, 187696417, 156820442, 237600210, 618812924, 153000239, 912364033,
254936966, 650298774, 982988140, 649258331, 566444626, 201481721, 492943390, 1061953081, 492672963, 960519711};
vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
int mult_[] = {1036482037, 583219072, 819168094, 253755052, 548208982, 401830167, 638626082, 43642932, 123607749, 485521178,
860368129, 30334704, 219771462, 733375600, 130839219, 415503960, 294132484, 1044831462, 256910484, 198852170};
vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
int add_[] = {889169006, 604831366, 967292994, 980686280, 844875791, 1027687492, 357734882, 295879743, 48284748, 421729100,
1049536313, 327207332, 948053446, 271229570, 664579359, 795815285, 842856528, 876662975, 675611938, 634229925};
vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
int _ = 8971965;
END
CASE(5)
int M = 1073741824;
int count_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
int first_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
int mult_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
int add_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
int _ = -1;
END
CASE(5)
int M = 1073741824;
int count_[] = {1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000,1000000};
vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
int first_[] = {775899,967700,946244,694562,767949,840507,668387,555565,884003,535966,934297,533923,585935,705980,506559,312277,271385,969286,803240,836682,693444,383269,412055,466183,462416,608005,144157,218468,961299,684785,324885,629586,362746,376166,666757,591939,599620,827159,650578,164404,229593,229537,132416,418569,454026,241609,23476,898462,433801,933810};
vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
int mult_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
int add_[] = {227399,73015,235546,945352,318629,384458,55809,766035,530600,755410,601579,841014,823193,223692,508381,636658,788171,265961,119515,822571,869554,564235,312051,105107,625704,480200,761095,588825,745857,74091,897771,900844,174101,352520,437181,680487,550423,923744,591847,998330,494389,171179,983838,494437,3604,940306,963263,854327,337255,802996};
vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
int _ = -1;
END
/*
CASE(6)
int M = ;
int count_[] = ;
vector <int> count(count_, count_+sizeof(count_)/sizeof(*count_));
int first_[] = ;
vector <int> first(first_, first_+sizeof(first_)/sizeof(*first_));
int mult_[] = ;
vector <int> mult(mult_, mult_+sizeof(mult_)/sizeof(*mult_));
int add_[] = ;
vector <int> add(add_, add_+sizeof(add_)/sizeof(*add_));
int _ = ;
END
*/
}
// END CUT HERE