In Byteland's train station, there are $n$ stations and $m$ trains in total. For each train, it will start from station $x_i$ at the moment $p_i$ and arrive at station $y_i$ at the moment $q_i$. Note that we can only take the train $i$ at the moment $p_i$ as well as get off at the moment $q_i$.

Starting from station $1$, Kevin is going to station $n$ by train. To reach his destination, he can do multiple transfers. Specifically, we can transfer from train $u$ to train $v$ if $y_u=x_v$ and $q_u\le p_v$. In this case, Kevin will have to wait for $p_v-q_u$ moments and take train $v$ at the moment $p_v$.

Let's evaluate Kevin's unhappiness as the value $W$.

Each time when Kevin has to wait for $t$ moments in a transfer process, $W$ will be increased by $A{t}^2+Bt+C$ ($A,B,C$ are three given constraints). Specifically, we consider the process between the moment $0$ and the moment getting on the first train also as a transfer, which means the waiting time needs to be taken into account.

Secondly, if Kevin reaches station $n$ at the moment of $z$, $W$ will be increased by $z$.

Please minimize Kevin's unhappiness value $W$. We guarantee that there is at least one possible plan to arrive at station $n$.

Input Specification

The first line contains $5$ integers $n,m,A,B,C$.

For the following $m$ lines, each line contains $x_i,y_i,p_i,q_i$, indicating the information of train $i$.

Constraints

All of the test cases satisfy $2\le n\le {10}^5$, $1\le m\le 2\times {10}^5$, $0\le A\le 10$, $0\le B,C\le {10}^6$, $1\le x_i,y_i\le n$, $x_i\ne y_i$, $0\le p_i<q_i\le {10}^3$.

Test Case	$n$	$m$	$A,B,C$	Others
1~2	$\le 100$	$=n-1$	None	$y_i=x_i+1$
3~4		$\le 100$	$A=B=C=0$
5~8	$\le 2000$	$\le 4000$		$x_i<y_i$
9			$A=B=0$
10			$A=0$
11~14			None	None
15	$\le {10}^5$	$\le 2\times {10}^5$	$A=B=0$
16~17			$A=0$
18~20			None

Output Specification

Please output an integer on one line, indicating the minimum possible value of $W$.

Sample Input 1

3 4 1 5 10
1 2 3 4
1 2 5 7
1 2 6 8
2 3 9 10

Sample Output 1

94