There are $n$ stations in the railway system of Cat Country, numbered $1$ to $n$. A cat plans to start from station $1$ and take trains to return to its home at station $n$. It has queried the available trains, of which there are $m$ in total, numbered $1$ to $m$. The cat arrives at station $1$ at time $0$. For train $i$, 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 train $i$ at time $p_i$ and must disembark at time $q_i$.

The cat can reach station $n$ through multiple transfers. A transfer refers to two trains, say train $u$ and train $v$. If $y_u = x_v$ and $q_u \le p_v$, the cat can take train $u$, wait at station $y_u$ for $p_v - q_u$ time units, and then board train $v$ at time $p_v$.

The cat only wants to return home while minimizing the trouble encountered along the way, which it measures using a "frustration value."

• The cat incurs frustration while waiting at stations. For a single wait of $t$ ($t \ge 0$) time units, the frustration value increases by $At^2 + Bt + C$, where $A, B, C$ are given constants. Note: The time the cat spends at station $1$ from time $0$ until it boards the first train also counts as a wait.
• If the cat finally arrives at station $n$ at time $z$, the frustration value increases by an additional $z$.

Formally, if the cat takes a total of $k$ trains, the sequence of train numbers taken can be represented as $s_1, s_2, \dots, s_k$. This plan is called a feasible route if and only if it satisfies the following two conditions:

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

For this route, the total frustration value incurred by the cat is: $$q_{s_k} + (A \cdot p_{s_1}^2 + B \cdot p_{s_1} + C) + \sum_{j=1}^{k-1} \left( A(p_{s_{j+1}} - q_{s_j})^2 + B(p_{s_{j+1}} - q_{s_j}) + C \right)$$

The cat wants to minimize its frustration value. Please help it find the minimum frustration value among all feasible routes. It is guaranteed that at least one feasible route exists.

Input

The input is read from the file route.in.

The first line contains five integers $n, m, A, B, C$, with the variables defined as in the problem description.

The next $m$ lines each contain four integers $x_i, y_i, p_i, q_i$, representing the departure station, arrival station, departure time, and arrival time of train $i$, respectively.

Output

The output is written to the file route.out.

Output a single integer representing the minimum frustration value.

Examples

Input 1

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

Output 1

94

Note 1

There are three feasible routes: 1. Taking trains $1$ and $4$ in sequence, the frustration value is: $10 + (1 \times 3^2 + 5 \times 3 + 10) + (1 \times (9 - 4)^2 + 5 \times (9 - 4) + 10) = 104$ 2. Taking trains $2$ and $4$ in sequence, the frustration value is: $10 + (1 \times 5^2 + 5 \times 5 + 10) + (1 \times (9 - 7)^2 + 5 \times (9 - 7) + 10) = 94$ 3. Taking trains $3$ and $4$ in sequence, the frustration value is: $10 + (1 \times 6^2 + 5 \times 6 + 10) + (1 \times (9 - 8)^2 + 5 \times (9 - 8) + 10) = 102$ The minimum frustration value is $94$.

Input 2

4 3 1 2 3
1 2 2 3
2 3 5 7
3 4 7 9

Output 2

34

Examples 3, 4, 5

See the files route/route3.in and route/route3.ans, route/route4.in and route/route4.ans, and route/route5.in and route/route5.ans in the contestant directory. These examples correspond to the data types of the final test cases $5 \sim 8$, $11 \sim 14$, and $18 \sim 20$, respectively.

Constraints

For all test cases: $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 \neq y_i, 0 \le p_i < q_i \le 10^3$

The specific constraints for each test case are shown in the table below: