Motorways

Byteland is covered by a dense network of paid two-way motorways. Each motorway connects two cities. The toll changes from day to day and depends both on which motorway is taken and on the direction of travel. Over the days each toll changes in a linear way: for every motorway and every direction there is a constant $p$ such that the toll for that direction changes by $p$ each day. The constant $p$ may be negative (the toll decreases), zero (the toll stays the same), or positive (the toll increases). All tolls change at midnight.

ByteGuy lives in city $a$ and wants to visit his friend, who lives in city $b$. On a single day he must drive from $a$ to $b$ and then back from $b$ to $a$. Being thrifty, he wants to make the trip on the day when the total cost of using the motorways is as small as possible. He must visit his friend no later than the $d$-th day.

The motorway network of Byteland is so well developed that it is possible to travel between any pair of cities, and between each pair of cities there is at most one direct connection. Byteland is a small country, so using the cheapest route he can always drive to city $b$ and return home within a single day. During the first $d$ days every toll is guaranteed to be positive.

Write a program that:

• reads the descriptions of the motorways together with ByteGuy's home city $a$, his friend's city $b$, and the number of days $d$;
• finds the minimum cost of driving from $a$ to $b$ and back on one of the first $d$ days;
• writes the result to standard output.

The first line contains five integers $n$, $m$, $a$, $b$, $d$ ($2 \le n \le 100\,000$, $1 \le m \le 100\,000$, $2 \le d \le 10\,000$), where $n$ is the number of cities, $m$ is the number of motorways, $a$ is ByteGuy's home city, $b$ is his friend's city, and $d$ is the number of days within which the trip must be made. The cities are numbered from $1$ to $n$, and $a$ and $b$ are different.

Each of the next $m$ lines describes one motorway with six integers $n_1$, $n_2$, $c_1$, $p_1$, $c_2$, $p_2$. Cities $n_1$ and $n_2$ are the endpoints of the motorway. $c_1$ and $c_2$ are the tolls on the first day for driving from $n_1$ to $n_2$ and from $n_2$ to $n_1$, respectively. On each following day the first toll changes by $p_1$ and the second toll changes by $p_2$. During the considered period (days $1$ through $d$) every toll is positive and at most $10\,000$.

Print a single integer: the minimum cost of driving from $a$ to $b$ and back on one of the first $d$ days.

In the figure above, to distinguish the costs of the two travel directions, each motorway is drawn as a pair of directed edges. The pair of numbers next to each edge gives the toll on the first day and the daily change of that toll.

Taking the route $1 \to 2 \to 3 \to 4 \to 1$ on the second day costs $23$.