Problem: You have a long fence which consists of n sections. Unfortunately, it is not painted, so you decided to hire q painters to paint it. i-th painter will paint all sections x such that l_i ≤ x ≤ r_i.

Unfortunately, you are on a tight budget, so you may hire only q - 2 painters. Obviously, only painters you hire will do their work.

You want to maximize the number of painted sections if you choose q - 2 painters optimally. A section is considered painted if at least one painter paints it.

Input

The first line contains two integers n and q (3 ≤ n, q ≤ 5000) — the number of sections and the number of painters availible for hire, respectively.

Then q lines follow, each describing one of the painters: i-th line contains two integers l_i and r_i (1 ≤ l_i ≤ r_i ≤ n).

Output

Print one integer — maximum number of painted sections if you hire q - 2 painters.

Examples

Input


7 5
1 4
4 5
5 6
6 7
3 5


Output


7


Input


4 3
1 1
2 2
3 4


Output


2


Input


4 4
1 1
2 2
2 3
3 4


Output


3

Solution (in JAVA):

Solution:
import java.io.BufferedReader;
import java.io.InputStreamReader;
import java.util.*; 

public class Main {

    public static class Worker implements Comparable<Worker>{
        public final int id;
        public int score;
        public final HashMap<Worker, Integer> influence;
        
        public Worker(int id)
        {
            this.id = id;
            this.score = 0;
            this.influence = new HashMap<>();
        }
        
        public void increaseInfluence(Worker coworker, int score)
        {
            influence.computeIfPresent(coworker, (k,v) -> v + score);
            influence.putIfAbsent(coworker, score);
        }
        
        /*public int getCombinedScore(Worker other)
        {
            int result = this.score + other.score;
            if (influence.containsKey(other))
            {
                result += influence.get(other);
            }
            return result;
        }*/
        
        public Solution getMinInfluence()
        {
            int minScore = Integer.MAX_VALUE;
            Solution bestSolution = null;
            for(Map.Entry<Worker, Integer> entry : influence.entrySet())
            {
                int combinedScore = this.score + entry.getKey().score + entry.getValue();
                if (combinedScore < minScore)
                {
                    minScore = combinedScore;
                    bestSolution = new Solution(this, entry.getKey(), combinedScore);
                }
            }
            return bestSolution;
        }
        
        @Override
        public int compareTo(Worker other)
        {
           return (this.score - other.score);
        }
    }
    
    public static class Boundary implements Comparable<Boundary> {
        public final Worker worker;
        public final int position;
        public final boolean isStart;
        
        public Boundary(Worker worker, int position, boolean isStart)
        {
            this.worker = worker;
            this.position = position;
            this.isStart = isStart;
        }
        
        @Override
        public int compareTo(Boundary other)
        {
           int result = this.position - other.position;
           if (result == 0 && this.isStart != other.isStart)
           {
               result = this.isStart ? -1 : 1;
           }
           return result;
        }
    }
    
    public static class Solution {
        public final Worker worker1;
        public final Worker worker2;
        public final int penalty;
        
        public Solution(Worker worker1, Worker worker2, int penalty)
        {
            this.worker1 = worker1;
            this.worker2 = worker2;
            this.penalty = penalty;
        }
    }
    
    public static void main(String[] args)
    {
    	final ArrayList<Worker> allWorkers = new ArrayList<>();
    	final ArrayList<Boundary> boundaries = new ArrayList<>();
    	int fenceLength = 0;
    	final int workerCount;
    	try
    	{
        	BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        	String[] header = br.readLine().split(" ");
        	fenceLength = Integer.parseInt(header[0]);
        	workerCount = Integer.parseInt(header[1]);
        	for (int i = 0; i < workerCount; ++i)
        	{
        	    String[] range = br.readLine().split(" ");
        	    Worker worker = new Worker(i);
        	    allWorkers.add(worker);
        	    Boundary start = new Boundary(worker, Integer.parseInt(range[0]), true);
        	    Boundary end = new Boundary(worker, Integer.parseInt(range[1]), false);
        	    boundaries.add(start);
        	    boundaries.add(end);
        	}
    	}
    	catch (Exception e)
    	{
    	    System.out.println("Exception: " + e);
    	}
    	
    	Collections.sort(boundaries);
    	
    	ArrayList<Worker> workers = new ArrayList<>();
    	Boundary lastBoundary = null;
    	int lastRemovedPos = 0;
    	int lastEmpty = 1;
    	int totalEmpty = 0;
    	for (int i = 0; i < boundaries.size(); ++i)
    	{
	        Boundary currentBoundary = boundaries.get(i);
            //System.out.println("p: " + currentBoundary.position + ", w: " + currentBoundary.worker.id + ", s: " + currentBoundary.isStart);
            if (workers.size() == 0)
            {
                if (currentBoundary.position > lastEmpty)
                {
                    totalEmpty += currentBoundary.position - lastEmpty;
                }
            }
            else if (workers.size() == 1)
            {
                workers.get(0).score += 
                    (workers.contains(currentBoundary.worker) ? 1 : 0)
                    + (lastRemovedPos == lastBoundary.position ? -1 : 0)
                    + (currentBoundary.position - lastBoundary.position);
                //System.out.println("curr_p: " + currentBoundary.position + ", last_p: " + lastBoundary.position + ", eq: " + (currentBoundary.worker == lastBoundary.worker));
                //System.out.println("score_inc: " + workers.get(0).id + ", by: " + ((workers.contains(currentBoundary.worker) ? 1 : 0) + (lastRemovedPos == lastBoundary.position ? -1 : 0) + currentBoundary.position - lastBoundary.position));
            }
            else if (workers.size() == 2)
            {
                workers.get(0).increaseInfluence(
                    workers.get(1),
                    (workers.contains(currentBoundary.worker) ? 1 : 0) 
                    + (lastRemovedPos == lastBoundary.position ? -1 : 0)
                    + (currentBoundary.position - lastBoundary.position)
                );
                //System.out.println("over w1: " + workers.get(0).id + ", w2: " + workers.get(1).id + ", by: " + ((workers.contains(currentBoundary.worker) ? 1 : 0) + (lastRemovedPos == lastBoundary.position ? -1 : 0) + currentBoundary.position - lastBoundary.position));
            }
           
            if (currentBoundary.isStart)
            {
                workers.add(currentBoundary.worker);
            }
            else
            {
                workers.remove(currentBoundary.worker);
                lastRemovedPos = currentBoundary.position;
                lastEmpty = currentBoundary.position + 1;
            }
            lastBoundary = currentBoundary;
    	}
    	if (lastBoundary != null && fenceLength > lastBoundary.position)
        {
            totalEmpty += fenceLength - lastBoundary.position;
        }
    	
    	Collections.sort(allWorkers);
    	
    	int minScore = Integer.MAX_VALUE;
    	Solution bestSolution = null;
    	for (int i = 0; i < allWorkers.size(); ++i)
    	{
    	    Worker worker1 = allWorkers.get(i);
    	    if (minScore <= worker1.score)
    	    {
    	        break;
    	    }
    	    Solution overlapSolution = worker1.getMinInfluence();
    	    if (overlapSolution != null && overlapSolution.penalty < minScore)
    	    {
    	        minScore = overlapSolution.penalty;
    	        bestSolution = overlapSolution;
    	        //System.out.println("o w1: " + bestSolution.worker1.id + ", w2: " + bestSolution.worker2.id + ", penalty: " + bestSolution.penalty);
    	    }
    	    for (int j = i+1; j < allWorkers.size(); ++j)
    	    {
    	        Worker worker2 = allWorkers.get(j);
    	        if (worker1.influence.containsKey(worker2) || worker2.influence.containsKey(worker1))
    	        {
    	            continue;
    	        }
    	        int score = worker1.score + worker2.score;
    	        if (score < minScore)
    	        {
    	            minScore = score;
    	            bestSolution = new Solution(worker1, worker2, score);
    	            //System.out.println("w1: " + bestSolution.worker1.id + ", w2: " + bestSolution.worker2.id + ", penalty: " + bestSolution.penalty);
    	        }
    	    }
    	}
    	//System.out.println("w1: " + bestSolution.worker1.id + ", w2: " + bestSolution.worker2.id + ", penalty: " + bestSolution.penalty);
    	//System.out.println("empty: " + totalEmpty);
    	//System.out.println("result: " + (totalEmpty + bestSolution.penalty));
    	System.out.println(fenceLength - (totalEmpty + bestSolution.penalty));
    }
}