Rahyab

SpongeBob founded a company called Rahyab-Tech after he finished his studies. The company built a mobile app called Rahyab that tells drivers which roads to take between cities. Rahyab caught on, and every driver now uses it on the road.

The hardest case SpongeBob has to handle is the Friday traffic from Motel-Ghu to Tehran. A route starts at Motel-Ghu, passes through some intermediate cities along the roads, and ends at Tehran. Every road is one directional and runs from one city to another city. Roads have no capacity limit. A road wears out faster when more cars drive on it, so the government charges every car by the busiest road of its trip. The surveillance system counts the cars that drive on each road during the day, and a car that drove on roads $r_1, \ldots, r_k$ is charged $\max\{t_{r_1}^2, \ldots, t_{r_k}^2\}$, where $t_{r_i}$ is the number of cars that drove on road $r_i$ that day.

Rahyab does not have to suggest the same route to every driver. Every driver follows the suggested route, but a driver who works out that another route would have cost less drops the app, and SpongeBob cannot accept that. So the plan has to be stable: once the routes are assigned, no driver can pay less by changing route alone while every other driver keeps the assigned route. When a driver moves from route $P$ to route $Q$, the counts move with the driver. Every road of $Q$ that is not on $P$ carries one more car, every road of $P$ that is not on $Q$ carries one car fewer, and the driver pays the square of the largest count among the roads of $Q$.

At the start of the day SpongeBob's program predicts the exact number of cars $C$ that travel from Motel-Ghu to Tehran. More than one stable plan can exist, and Rahyab uses a stable plan whose total charge over all cars is as small as possible. Given the map of roads and the number $C$, compute that total charge.

The input holds several test cases. Each test case starts with a line of five space separated integers $N$, $E$, $M$, $T$ and $C$. $N$ is the number of cities and $E$ is the number of roads ($2 \le N \le 500$, $0 \le E \le 100000$). The cities are numbered 1 through $N$. $M$ is the number of Motel-Ghu and $T$ is the number of Tehran ($1 \le M, T \le N$, $M \ne T$). $C$ is the number of trips from Motel-Ghu to Tehran on Friday ($0 \le C \le 10^6$). Each of the next $E$ lines holds two space separated integers $x_i$ and $y_i$ ($1 \le x_i, y_i \le N$), a one directional road from city $x_i$ to city $y_i$. Several roads can join the same pair of cities in the same direction, and each of them is a separate road with its own car count. At least one route from Motel-Ghu to Tehran exists. The input ends with a line holding five zeros, which is not a test case.

For each test case, print one line with the total charge over all cars under a stable plan whose total charge is smallest.