In Chelyabinsk lives a much respected businessman Nikita with a strange nickname "Boss". Once Nikita decided to go with his friend Alex to the Summer Biathlon World Cup. Nikita, as a very important person, received a token which allows to place bets on each section no more than on one competitor.

To begin with friends learned the rules: in the race there are n sections of equal length and m participants. The participants numbered from 1 to m. About each participant the following is known:

  * li — the number of the starting section, 
  * ri — the number of the finishing section (li ≤ ri),
  * ti — the time a biathlete needs to complete an section of the path,
  * ci — the profit in roubles. If the i-th sportsman wins on one of the sections, the profit will be given to the man who had placed a bet on that sportsman.



The i-th biathlete passes the sections from li to ri inclusive. The competitor runs the whole way in (ri - li + 1)·ti time units. It takes him exactly ti time units to pass each section. In case of the athlete's victory on k sections the man who has betted on him receives k·ci roubles.

In each section the winner is determined independently as follows: if there is at least one biathlete running this in this section, then among all of them the winner is the one who has ran this section in minimum time (spent minimum time passing this section). In case of equality of times the athlete with the smaller index number wins. If there are no participants in this section, then the winner in this section in not determined. We have to say that in the summer biathlon all the participants are moving at a constant speed.

We should also add that Nikita can bet on each section and on any contestant running in this section.

Help the friends find the maximum possible profit.

Input

The first line contains two integers n and m (1 ≤ n, m ≤ 100). Then follow m lines, each containing 4 integers li, ri, ti, ci (1 ≤ li ≤ ri ≤ n, 1 ≤ ti, ci ≤ 1000).

Output

Print a single integer, the maximal profit in roubles that the friends can get. In each of n sections it is not allowed to place bets on more than one sportsman.

Examples

Input

4 4
1 4 20 5
1 3 21 10
3 3 4 30
3 4 4 20


Output

60

Input

8 4
1 5 24 10
2 4 6 15
4 6 30 50
6 7 4 20


Output

105

Note

In the first test the optimal bet is: in the 1-2 sections on biathlete 1, in section 3 on biathlete 3, in section 4 on biathlete 4. Total: profit of 5 rubles for 1 section, the profit of 5 rubles for 2 section, profit of 30 rubles for a 3 section, profit of 20 rubles for 4 section. Total profit 60 rubles.

In the second test the optimal bet is: on 1 and 5 sections on biathlete 1, in the 2-4 sections on biathlete 2, in the 6-7 sections on athlete 4. There is no winner in the 8 section. Total: profit of 10 rubles for 1 section, the profit of 15 rubles for 2,3,4 section, profit of 10 rubles for a 5 section, profit of 20 rubles for 6, 7 section. Total profit 105 rubles.
import java.io.File;import java.io.FileInputStream;import java.io.FileNotFoundException;
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;
import java.security.AccessControlException;import java.util.List;import java.util.function.Function;
import java.util.stream.Collectors;import java.util.stream.IntStream;public class _p000069B {
static public void main(final String[] args) throws IOException{p000069B._main(args);}

static class p000069B extends Solver{public p000069B(){singleTest=true;}@Override public 
void solve()throws IOException{int n=sc.nextInt();int m=sc.nextInt();sc.nextLine();
Driver dr=new Driver();dr.configure(n);int[][]tree=new int[dr.getTreeLength()][3];
for(int $i0=0;$i0<m;$i0++){int l=sc.nextInt();int r=sc.nextInt();int t=sc.nextInt();
int c=sc.nextInt();sc.nextLine();int i=$i0+1;dr.setGetter(new DriverGetter(){@Override public 
void accept(int pos){if(tree[pos][0]==0 || tree[pos][0]>t){tree[pos][0]=t;tree[pos][1]
=c;tree[pos][2]=i;}}});dr.get(l-1,r);}int res=0;for(int i=0;i<n;i++){int min=0;int 
min_profit=0;int min_index=0;int node=dr.getStart()+i;while(node>=0){if(tree[node][0]
>0){if(min==0 || tree[node][0]<min){min=tree[node][0];min_profit=tree[node][1];min_index
=tree[node][2];}else if(tree[node][0]==min && min_index>tree[node][2]){min_profit
=tree[node][1];min_index=tree[node][2];}}if(node==0){break;}node=(node-1)/2;}res
+=min_profit;}pw.println(res);}static public void _main(String[]args)throws IOException
{new p000069B().run();}}static class Driver{private int max_level;private int n2;
private int trlen;private int n;private DriverUpdater updater=null;private DriverInitializator 
setter=null;private DriverGetter getter=null;private DriverInitializator initializator
=null;private int get_result;private int get_pos;private boolean break_cycle=false;
private boolean right_to_left=false;final public void setUpdater(final DriverUpdater 
updater){this.updater=updater;}final public DriverUpdater getUpdater(){return updater;
}final public void setSetter(final DriverInitializator setter){this.setter=setter;
}final public DriverInitializator getSetter(){return setter;}final public void setGetter(final 
DriverGetter getter){this.getter=getter;}final public DriverGetter getGetter(){return 
getter;}final public void setInitializator(final DriverInitializator initializator)
{this.initializator=initializator;}final public DriverInitializator getInitializator()
{return initializator;}final public void configure(final int n){this.n=n;max_level
=(int)Math.ceil(Math.log(n)/Math.log(2));n2=1<<max_level;trlen=(n2<<1)-1;}final 
public String treeToString(final Function<Integer,String>itemToString){Function<Integer,
String>its=itemToString==null?p->"true":itemToString;StringBuilder sb=new StringBuilder();
int[]start=new int[]{0};int stop=1;int[]w=new int[]{n2};sb.append("[");while(start[0]
<trlen){sb.append(IntStream.range(start[0],stop).mapToObj(p->(p-start[0])*w[0]<n
?its.apply(p):"-").collect(Collectors.joining(", ","(",")")));start[0]=stop;stop
=(stop<<1)+1;w[0]>>=1;}sb.append("]");return sb.toString();}final public void init()
{if(initializator!=null){for(int i=0;i<n;i++){initializator.accept(i,trlen-n2+i);
}}}final public void boot(){if(updater!=null){break_cycle=false;int end;int prev_end
=0;end=trlen-n2+n-1;int start=trlen>>1;for(int p=start-1;p>=0;p--){if(p<start){prev_end
=end;end=(end-1)>>1;p=end;start>>=1;}int left=(p<<1)+1;updater.accept(QueryType.BOOT,
p,left,left<prev_end?left+1:-1);if(break_cycle){break;}}}}final public void boot(final 
int pos){if(updater!=null && pos<trlen-n2){int start=pos;int stop=pos+1;int next;
while((next=(start<<1)+1)<trlen-n2){start=next;stop=(stop<<1)+1;}int prev_end=trlen
-n2+n-1;int end=Math.min(stop-1,(prev_end-1)>>1);break_cycle=false;for(int p=end;
p>=pos;p--){int left=(p<<1)+1;updater.accept(QueryType.BOOT,p,left,left<prev_end
?left+1:-1);if(break_cycle){break;}if(p==start){prev_end=end;start>>=1;end=(end-
1)>>1;p=end+1;}}}}final public void breakCycle(){break_cycle=true;}final public 
void set(final int i){int p=trlen-n2+i;if(setter!=null){setter.accept(i,p);}break_cycle
=false;if(updater!=null){int end=trlen-n2+n-1;while(p>0){int left=((p & 1)==1)?p
:p-1;p=(p-1)>>1;updater.accept(QueryType.SET,p,left,left<end?left+1:-1);if(break_cycle)
{break;}end=(end-1)>>1;}}}final public boolean rightToLeft(){return right_to_left;
}private void get_ltr(final int pos,final int l,final int r,final int b,final int 
e){if(!break_cycle){if(b<r && e>l){int e1=Math.min(e,n);if(b>=l && e1<=r){if(getter
!=null){getter.accept(pos);}if(get_result==-1){get_result=pos;}else if(updater!=
null){updater.accept(QueryType.GET,trlen+get_pos,get_result,pos);get_result=trlen
+get_pos;get_pos ^=1;}}else if(e-b>1){int left=(pos<<1)+1;int m=(b+e)>>1;get_ltr(left,
l,r,b,m);get_ltr(left+1,l,r,m,e);}}}}private void get_rtl(final int pos,final int 
l,final int r,final int b,final int e){if(!break_cycle){if(b<r && e>l){int e1=Math.min(e,
n);if(b>=l && e1<=r){if(getter!=null){getter.accept(pos);}if(get_result==-1){get_result
=pos;}else if(updater!=null){updater.accept(QueryType.GET,trlen+get_pos,pos,get_result);
get_result=trlen+get_pos;get_pos ^=1;}}else if(e-b>1){int left=(pos<<1)+1;int m=
(b+e)>>1;get_rtl(left+1,l,r,m,e);get_rtl(left,l,r,b,m);}}}}final public int get(final 
int l,final int r){this.right_to_left=false;break_cycle=false;get_result=-1;get_pos
=0;get_ltr(0,l,r,0,n2);return get_result;}final public int get(final int l,final 
int r,final boolean right_to_left){this.right_to_left=right_to_left;break_cycle=
false;get_result=-1;get_pos=0;if(right_to_left){get_rtl(0,l,r,0,n2);}else{get_ltr(0,
l,r,0,n2);}return get_result;}final public int getLength(){return n2;}final public 
int getTreeLength(){return trlen;}final public int getStart(){return trlen-n2;}}
static interface DriverGetter{void accept(final int pos);}static interface DriverInitializator
{void accept(final int index,final int pos);}static interface DriverUpdater{void 
accept(final QueryType type,final int target,final int left,final int right);}static enum 
QueryType{BOOT,SET,GET}static class MyScanner{private StringBuilder cache=new StringBuilder();
int cache_pos=0;private int first_linebreak=-1;private int second_linebreak=-1;private 
StringBuilder sb=new StringBuilder();private InputStream is=null;public MyScanner(final 
InputStream is){this.is=is;}public String charToString(final int c){return String.format("'%s'",
c=='\n'?"\\n":(c=='\r'?"\\r":String.valueOf((char)c)));}public int get(){int res
=-1;if(cache_pos<cache.length()){res=cache.charAt(cache_pos);cache_pos++;if(cache_pos
==cache.length()){cache.delete(0,cache_pos);cache_pos=0;}}else{try{res=is.read();
}catch(IOException ex){throw new RuntimeException(ex);}}return res;}private void 
unget(final int c){if(cache_pos==0){cache.insert(0,(char)c);}else{cache_pos--;}}
public String nextLine(){sb.delete(0,sb.length());int c;boolean done=false;boolean 
end=false;while((c=get())!=-1){if(check_linebreak(c)){done=true;if(c==first_linebreak)
{if(!end){end=true;}else{cache.append((char)c);break;}}else if(second_linebreak!=
-1 && c==second_linebreak){break;}}if(end && c!=first_linebreak && c!=second_linebreak)
{cache.append((char)c);break;}if(!done){sb.append((char)c);}}return!done && sb.length()
==0?null:sb.toString();}private boolean check_linebreak(int c){if(c=='\n'|| c=='\r')
{if(first_linebreak==-1){first_linebreak=c;}else if(c!=first_linebreak && second_linebreak
==-1){second_linebreak=c;}return true;}return false;}public int nextInt(){return 
Integer.parseInt(next());}public long nextLong(){return Long.parseLong(next());}
public boolean hasNext(){boolean res=false;int c;while((c=get())!=-1){if(!check_linebreak(c)
&& c!=' '&& c!='\t'){res=true;unget(c);break;}}return res;}public String next(){
sb.delete(0,sb.length());boolean started=false;int c;while((c=get())!=-1){if(check_linebreak(c)
|| c==' '|| c=='\t'){if(started){unget(c);break;}}else{started=true;sb.append((char)c);
}}return sb.toString();}public int nextChar(){return get();}public boolean eof()
{int c=get();boolean res=false;if(c!=-1){unget(c);}else{res=true;}return res;}public 
double nextDouble(){return Double.parseDouble(next());}}static abstract class Solver
{protected String nameIn=null;protected String nameOut=null;protected boolean singleTest
=false;protected MyScanner sc=null;protected PrintWriter pw=null;private int current_test
=0;private int count_tests=0;protected int currentTest(){return current_test;}protected 
int countTests(){return count_tests;}private void process()throws IOException{if(!singleTest)
{count_tests=sc.nextInt();sc.nextLine();for(current_test=1;current_test<=count_tests;
current_test++){solve();pw.flush();}}else{count_tests=1;current_test=1;solve();}
}abstract protected void solve()throws IOException;public void run()throws IOException
{boolean done=false;try{if(nameIn!=null){if(new File(nameIn).exists()){try(FileInputStream 
fis=new FileInputStream(nameIn);PrintWriter pw0=select_output();){select_output();
done=true;sc=new MyScanner(fis);pw=pw0;process();}}else{throw new RuntimeException("File "
+new File(nameIn).getAbsolutePath()+" does not exist!");}}}catch(IOException | AccessControlException 
ex){}if(!done){try(PrintWriter pw0=select_output();){sc=new MyScanner(System.in);
pw=pw0;process();}}}private PrintWriter select_output()throws FileNotFoundException
{if(nameOut!=null){return new PrintWriter(nameOut);}return new PrintWriter(System.out);
}}static abstract class Tester{static public int getRandomInt(final int min,final 
int max){return(min+(int)Math.floor(Math.random()*(max-min+1)));}static public long 
getRandomLong(final long min,final long max){return(min+(long)Math.floor(Math.random()
*(max-min+1)));}static public double getRandomDouble(final double min,final double 
maxExclusive){return(min+Math.random()*(maxExclusive-min));}abstract protected void 
testOutput(final List<String>output_data);abstract protected void generateInput();
abstract protected String inputDataToString();private boolean break_tester=false;
protected void beforeTesting(){}protected void breakTester(){break_tester=true;}
public boolean broken(){return break_tester;}}}
