public static void main(String[] args) throws Exception{
        BufferedReader br = new BufferedReader(new FileReader("empty.in"));
        PrintWriter out = new PrintWriter(new BufferedWriter(new FileWriter("empty.out")));

        StringTokenizer st = new StringTokenizer(br.readLine());
        n = Integer.parseInt(st.nextToken());
        int k = Integer.parseInt(st.nextToken());
        while(k-->0){
            st = new StringTokenizer(br.readLine());
            int x = Integer.parseInt(st.nextToken());
            int y = Integer.parseInt(st.nextToken());
            long A = Integer.parseInt(st.nextToken());
            int B = Integer.parseInt(st.nextToken());
            for(int i=1; i<=y; i++){
                int preferred = (int)(A*i+B)%n;
                if(map.isEmpty()){
                    map.put(preferred, end(preferred, x));
                    continue;
                }
                Map.Entry<Integer,Integer> prev = prev(preferred);
                int start, begin, end=0;
                ArrayList<Integer> deleted = new ArrayList<Integer>();
                if(isInside(preferred,prev)){
                    start = nextAdj(prev);
                    begin = prev.getKey();
                    deleted.add(prev.getKey());
                } else{
                    start = preferred;
                    begin = preferred;
                }
                while(x>0){
                    Map.Entry<Integer, Integer> next = next(start);
                    int available = length(start, prevAdj(next));
                    if(x>available){
                        x = x-available;
                        start=nextAdj(next);
                        deleted.add(next.getKey());
                    } else{
                        end = end(start,x);
                        if(end == prevAdj(next)){
                            end = next.getValue();
                            deleted.add(next.getKey());
                        }
                        x = 0;
                    }
                }
                for(int key : deleted) map.remove(key);
                map.put(begin, end);
            }
        }
        int result = Math.min(prevAdj(map.firstEntry()), nextAdj(map.lastEntry()));
        result = Math.min(result, nextAdj(map.firstEntry())); // when first starts at 0;
        out.println(result);
        out.close();
    }