Cat's Railway Journey

In Catland, there are \(n\) stations numbered from 1 to \(n\). A little cat wants to travel from station 1 (its starting point at time 0) to station \(n\) (where its cozy den is located) by taking one or more trains. There are \(m\) available trains numbered from 1 to \(m\). For the \(i\)th train, it departs from station \(x_i\) at time \(p_i\) and arrives directly at station \(y_i\) at time \(q_i\). The cat can only board the \(i\)th train exactly at time \(p_i\) and must get off at time \(q_i\). It can transfer between trains: if one train ends at station \(s\) (i.e. \(y_u=s\)) and another train departs from station \(s\) (i.e. \(x_v=s\)) at a time \(p_v\ge q_u\), the cat may wait from time \(q_u\) to \(p_v\) and then board the next train.

While waiting, the cat becomes annoyed. A waiting period lasting \(t\) time units (with \(t\ge0\)) increases the cat's annoyed value by:

[ A\times t^2+B\times t+C ]

Notice that the cat also waits at station 1 before boarding its first train (waiting from time 0 to \(p_{s_1}\)). Furthermore, if the cat finally arrives at station \(n\) at time \(z\) (i.e. \(z=q_{s_k}\) on its last train), the total annoyed value increases by \(z\) (this is added after all waiting costs).

Formally, suppose the cat boards a sequence of \(k\) trains with indices \(s_1, s_2, \ldots, s_k\) satisfying:

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

Then the total annoyed value is computed as:

[ q_{s_k}+\Bigl(A\times p_{s_1}^2+B\times 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) ]

Your task is to determine the minimum total annoyed value among all feasible routes. It is guaranteed that at least one valid route exists.

inputFormat

The first line contains five integers \(n\), \(m\), \(A\), \(B\), \(C\) separated by spaces.

Each of the next \(m\) lines contains four integers \(p_i\), \(x_i\), \(q_i\), \(y_i\) describing a train that departs from station \(x_i\) at time \(p_i\) and arrives at station \(y_i\) at time \(q_i\).

outputFormat

Output a single integer representing the minimum total annoyed value the cat can achieve.

sample

3 3 1 1 1
1 1 2 2
3 2 4 3
2 1 5 3

10