#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
