NOI '19 P1 - Route

View as PDF

Submit solution

Points: 25 (partial)
Time limit: 1.0s
Memory limit: 512M

Problem type

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 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 xi,yi,pi,qi, indicating the information of train i.

Constraints

All of the test cases satisfy 2n105, 1m2×105, 0A10, 0B,C106, 1xi,yin, xiyi, 0pi<qi103.

Test CasenmA,B,COthers
1~2100=n1Noneyi=xi+1
3~4100A=B=C=0
5~820004000xi<yi
9A=B=0
10A=0
11~14NoneNone
151052×105A=B=0
16~17A=0
18~20None

Output Specification

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

Sample Input 1

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

Sample Output 1

Copy
94

Comments

There are no comments at the moment.