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

Note: An additional test case was added to each existing test case from 15 to 20 in the same batch to hack unintended solutions. The issue was noticed by marsxiang5902.

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