Chef and Girls

All submissions for this problem are available.
Read problems statements in Mandarin Chinese, Russian and Vietnamese as well.
Chef has a problem  he likes a girl but she has 32 secrets and N friends (also girls).
Chef has enumerated each girl from 1 to N, Chef's crush has the number 1.
Now he consider all girls as nodes of a directed graph. If one girl has an edge directed towards another girl, the former tells all the secrets she knows to the latter. Edges are oriented, so if one girl is sharing secrets with another, it doesn't imply the same relation in the reverse direction. Also, there are no cycles in the graph.
Each girl (except Chef's crush) has only one edge emanating from her, or doesn't have any edges emanating from her at all. Each girl listens to at most one girl. In other words, for each girl, there is only one girl who reveals secrets to her, or there are no such girls at all. Each edge has two integers assigned to it, specifying the range of interest. If girl A knows secrets in the range [1020] and an edge directed towards girl B with a range of interest [215] then girl B will know secrets in the range [1015], which is, evidently, an intersection of the range of secrets and the interest range.
Chef's crush has all the [132] secrets, other girls just listen to her and then gossip around (share those secrets). If a girl doesn't have an edge emanating from her, she tells all the secrets she knows to Chef.
Chef can perform operations of the following kind: take some edge, and extend its range of interest by one (to the left or the right). He wants to know the minimal number of operations he needs to perform in order to collect all the secrets.
Input
 The first line contains two integers N and M denoting the number of girls and ribs appropriately.
 Each of next M lines describe an edge, and contains four integers — i, j, l, r — meaning that there is an oriented edge from i to j with a range of interest [lr].
Output
 In a single line, output a single integer: the answer.
Constraints
 1 ≤ N, M ≤ 10^5
 1 ≤ i < j ≤ N
 1 ≤ l ≤ r ≤ 32
Subtasks
 Subtask N, M ≤ 10. Points: 10
 Subtask N, M ≤ 10^3. Points: 20
 Subtask Original constraints. Points: 70
Example
Input: 5 4 1 2 10 15 1 3 10 16 2 4 1 1 3 5 10 15 Output: 50
Explanation
Example case 1.
Without any changes made by Chef, we will have the following knowledge propagation: Girl 1 knows [132]. Girl 2 knows [1015] (intersection of [132] and [1015]). Girl 3 knows [1016] (intersection of [132] and [1016]). Girl 4 knows [] (intersection of [1015] and [11]). Girl 5 knows [1015] (intersection of [1016] and [1015]). So Chef can collect secrets [1015] only. Here is the solution: 1. Change 1 2 10 15 to 1 2 1 15 (by applying the operation 9 times). 2. Change 2 4 1 1 to 2 4 1 9 (by applying the operation 8 times). 3. Change 1 3 10 16 to 1 3 10 32 (by applying the operation 16 times). 3. Change 3 5 10 15 to 1 3 10 32 (by applying the operation 17 times). Now, all secrets in the range [19] will go through 124 and all secrets in the range [1032] will go through 135, finally reaching Chef. And the total cost is 50.
Author:  berezin 
Tester:  xcwgf666 
Editorial  http://discuss.codechef.com/problems/CHEFGIRL 
Tags  berezin, dec15, directed, dynamicprogramming, graphs, medium 
Date Added:  25102015 
Time Limit:  1 sec 
Source Limit:  50000 Bytes 
Languages:  C, CPP14, JAVA, PYTH, PYTH 3.5, PYPY, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, SCM chicken, CLOJ, FS 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions
HELP
If you are still having problems, see a sample solution here. 