NOI '19 P1 - Route

View as PDF

Submit solution

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

Problem type
Allowed languages
Ada, Assembly, Awk, Brain****, C, C#, C++, COBOL, CommonLisp, D, Dart, F#, Forth, Fortran, Go, Groovy, Haskell, Intercal, Java, JS, Kotlin, Lisp, Lua, Nim, ObjC, OCaml, Octave, Pascal, Perl, PHP, Pike, Prolog, Python, Racket, Ruby, Rust, Scala, Scheme, Sed, Swift, TCL, Text, Turing, VB, Zig

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 need 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.


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 CasenmA,B,COthers
1~2\le 100= n - 1Noney_i = x_i + 1
3~4\le 100A = B = C = 0
5~8\le 2\,000\le 4\,000x_i < y_i
9A = B = 0
10A = 0
15\le 10^5\le 2\times 10^5A = B = 0
16~17A = 0

Output Specification

Please output an integer on one line, indication 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



There are no comments at the moment.