Minimizing Cat’s Frustration on the Railway

In the Cat Kingdom, there are n stations numbered from 1 to n. A little cat wants to travel from station 1 to station n (where its cat home is) using one or more trains. At time 0 the cat is at station 1. There are m trains available (numbered from 1 to m). For the i-th train, the cat can board it at time \(p_i\) at station \(x_i\), and the train reaches station \(y_i\) exactly at time \(q_i\). The cat must board a train exactly at its departure time and disembark exactly at its arrival time. A transfer between two trains is allowed if for trains \(u\) and \(v\), we have \(y_u = x_v\) and \(q_u \le p_v\); that is, after finishing train \(u\) at station \(y_u\), the cat can wait until time \(p_v\) to board train \(v\).

Waiting at any station increases the cat’s frustration level. If the cat waits for \(t \,(t \ge 0)\) time units continuously, the frustration increases by:

[ A t^2 + B t + C, ]

where \(A, B, C\) are given constants. Note that the waiting time before boarding the first train (i.e. from time 0 until \(p_{s_1}\)) is also counted.

If the cat finally arrives at station n at time \(z\), its frustration increases by \(z\) as well.

Formally, suppose the cat takes \(k\) trains with indices \(s_1, s_2, \dots, s_k\) forming a valid route, meaning:

• \(x_{s_1} = 1\) and \(y_{s_k} = n\),
• For every \(1 \le j < k\), we have \(y_{s_j} = x_{s_{j+1}}\) and \(q_{s_j} \le p_{s_{j+1}}\).

The total frustration of this route is:

[ q_{s_k} + \Bigl( A,p_{s_1}^2 + B,p_{s_1} + C \Bigr) + \sum_{j=1}^{k-1} \Bigl( A,(p_{s_{j+1}}-q_{s_j})^2 + B,(p_{s_{j+1}}-q_{s_j}) + C \Bigr). ]

Help the cat to choose a valid route that minimizes its total frustration. It is guaranteed that at least one valid route exists.

inputFormat

The first line of input contains five integers: n \(\, (2 \le n)\), m (the number of trains), and the constants \(A\), \(B\), and \(C\). Each of the following m lines contains four integers, describing a train:

• p_i \(\, (\) departure time \()\),
• q_i \(\, (q_{i} \ge p_{i})\) arrival time,
• x_i (departure station), and
• y_i (arrival station).

All values are integers. The cat starts at station 1 at time 0 and must reach station n.

outputFormat

Output a single integer, the minimum total frustration that the cat can achieve on a valid route.

sample

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

18