记录编号	84510	评测结果	AAAAAAAAAAA
题目名称	[USACO Nov13]空牛栏	最终得分	100
用户昵称	Chenyao2333	是否通过	通过
代码语言	C++	运行时间	1.240 s
提交时间	2013-12-14 15:57:27	内存使用	14.60 MiB

//N K
//X Y A B
//f(i)=(A*i+B) mod N

#include<stdio.h>
#include<deque>
using namespace std;

const int MAXN=3000000+10;
typedef long long LL;

int N;
int niu_n[MAXN]={0};

void open(){
	freopen("empty.in","r",stdin);
	freopen("empty.out","w",stdout);
}

inline int f(LL i,LL A,LL B){
	return ((A%N)*(i%N)+(B%N))%N;
}

void read(){
	int k;
	int x,y,a,b;
	scanf("%d %d",&N,&k);
	for(int i=0;i<k;i++){
		scanf("%d %d %d %d",&x,&y,&a,&b);
		for(int j=1;j<=y;j++){
			niu_n[f(j,a,b)]+=x;
		}
	}
}
bool niu[MAXN]={0};

bool ok=true;

inline int inc(int& i){
	i++;
	if(i>=N)ok=false;
	i%=N;
}

int solve(){
	int tail=0;
	for(int i=0;i<N;i++){
		if(ok && tail<i){
			tail=i;
		}
		for(tail;niu_n[i];inc(tail)){
			if(!niu[tail]){
				niu_n[i]--;
				niu[tail]=true;
			}
		}
	}
	if(ok)tail=0;
	for(tail;niu[tail];tail++);
	return tail;
}

int main(){
	open();
	read();
	int ans=solve();
	printf("%d",ans);
	return 0;
}