J. Phone Lines
time limit per test
2 seconds
memory limit per test
1024 megabytes
input
standard input
output
standard output

Phone companies have recently changed the way they operate. Since you and your two teammates need to train together for online programming marathons, you want to calculate how much you will spend to contact them by phone.

There are $$$N$$$ phone companies in total, numbered from 1 to $$$N$$$. Each company $$$U$$$ may have multiple directed communication lines. Each such line starts at company $$$U$$$ and reaches every company in an interval $$$[L, R]$$$. The communication cost varies as follows: the cost to connect company $$$U$$$ to company $$$L$$$ is $$$X$$$, to company $$$L+1$$$ is $$$X + K$$$, to company $$$L+2$$$ is $$$X + 2 \times K$$$, and so on, up to company $$$R$$$, for which the cost is $$$X + (R - L) \times K$$$. More formally, the cost to connect company $$$U$$$ to company $$$i$$$ ($$$L \leq i \leq R$$$) is $$$X + (i - L) \times K$$$.

The cost of a path is the sum of the costs of the connections that form it. The cost of a phone call from a company $$$U$$$ to another company $$$V$$$ is the smallest cost among all paths from company $$$U$$$ to company $$$V$$$. A path may use no communication line at all; therefore, the cost of a call from a company to itself is $$$0$$$.

You use the services of company 1, while your two teammates use the services of companies $$$A$$$ and $$$B$$$. You need to calculate the minimum total cost to call both of your teammates, that is, the sum of the minimum costs of the calls from company 1 to companies $$$A$$$ and $$$B$$$. You can only train together if it is possible to call both teammates.

Input

The first line contains four integers $$$N$$$, $$$M$$$, $$$A$$$, and $$$B$$$ ($$$1 \leq N \leq 10^{5}$$$, $$$1 \leq M \leq 10^{5}$$$, $$$1 \leq A, B \leq N$$$), representing, respectively, the number of companies, the number of communication lines, and the company numbers of your two teammates. Companies $$$A$$$ and $$$B$$$ may be equal to each other and may also be equal to company 1.

Each of the following $$$M$$$ lines contains five integers $$$U$$$, $$$L$$$, $$$R$$$, $$$X$$$, and $$$K$$$ ($$$1 \leq U \leq N$$$, $$$1 \leq L \leq R \leq N$$$, $$$0 \leq X \leq 10^{13}$$$, $$$-10^{8} \leq K \leq 10^{8}$$$), describing a communication line that starts at company $$$U$$$ and reaches the companies in the interval $$$[L, R]$$$. It is guaranteed that $$$X + (R - L) \times K \geq 0$$$.

It is possible that $$$U$$$ belongs to the interval $$$[L, R]$$$.

Output

Print a single line containing an integer representing the minimum total cost to call both teammates. If it is not possible to call at least one of them, print $$$-1$$$.

Examples
Input
8 4 2 8
1 4 6 1 1
4 2 3 2 2
2 6 8 0 5
6 7 8 6 1
Output
13
Input
8 4 3 7
1 4 7 10 -2
6 5 8 0 1
4 1 2 3 0
3 1 5 4 6
Output
-1
Input
6 3 5 2
1 2 6 2 3
3 5 6 1 0
6 5 5 1 1
Output
8
Input
1 1 1 1
1 1 1 0 0
Output
0
Note

Explanation for example 1

The smallest cost to call from company $$$1$$$ to company $$$2$$$ is $$$3$$$, via the path $$$1 \to 4 \to 2$$$, whose connections cost $$$1$$$ and $$$2$$$. The smallest cost to call from company $$$1$$$ to company $$$8$$$ is $$$10$$$, via the path $$$1 \to 6 \to 8$$$, whose connections cost $$$3$$$ and $$$7$$$.

Therefore, the total cost to call both teammates is $$$3 + 10 = 13$$$.

Explanation for example 2

In this case, there is no path from company $$$1$$$ to company $$$3$$$, so the answer is $$$-1$$$.

Explanation for example 4

Both teammates use the services of company $$$1$$$. Since the minimum cost to call from company $$$1$$$ to itself is $$$0$$$, the total cost is $$$0$$$.