시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
1 초 512 MB 3 3 3 100.000%

문제

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

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 yu = xv and qupv. In this case, Kevin will have to wait for pvqu moments and take train v at the moment pv.

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 At2 + 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 need to be taken into account.

Secondly, if Kevin reaches station n at the moment of zW 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.

입력

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

For the following m lines, each line contains xi, yi, pi, qi, indicating the information of train i.

출력

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

제한

All of the test cases satisfy 2 ≤ n ≤ 105, 1 ≤ m ≤ 2×105, 0 ≤ A ≤ 10, 0 ≤ B, C ≤ 106, 1 ≤ xi, yin, xiyi, 0 ≤ pi < qi ≤ 103.

예제 입력 1

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

예제 출력 1

94