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 ~At^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 2\,000~	~\le 4\,000~		~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