Rahyab

스펀지밥은 학업을 마친 뒤 Rahyab-Tech라는 회사를 세웠다. 이 회사는 도시 사이를 오갈 때 어떤 도로로 가야 하는지 운전자에게 알려 주는 모바일 앱 Rahyab을 만들었다. Rahyab이 널리 퍼지면서 이제 모든 운전자가 이 앱을 쓰면서 운전한다.

스펀지밥이 다뤄야 하는 가장 어려운 상황은 금요일에 Motel-Ghu에서 Tehran으로 가는 차량의 경로를 정하는 일이다. 경로는 Motel-Ghu에서 출발해 도로를 따라 중간 도시 몇 곳을 지난 뒤 Tehran에서 끝난다. 도로는 모두 한 도시에서 다른 도시로 가는 일방통행이고, 통행량 상한은 없다. 많은 차가 지날수록 도로가 빨리 망가지기 때문에 정부는 각 차량이 그날 지난 도로 중 가장 붐빈 도로를 기준으로 요금을 매긴다. 감시 시스템은 하루 동안 각 도로를 지난 차량 수를 센다. 도로 $r_1, \ldots, r_k$를 지난 차량은 $\max\{t_{r_1}^2, \ldots, t_{r_k}^2\}$를 낸다. 여기서 $t_{r_i}$는 그날 도로 $r_i$를 지난 차량 수다.

Rahyab이 모든 운전자에게 같은 경로를 알려 줄 필요는 없다. 운전자는 안내받은 경로를 그대로 따르지만, 다른 경로로 갔다면 요금을 덜 냈다는 사실을 알아차린 운전자는 앱을 떠나 버린다. 스펀지밥은 이를 용납할 수 없다. 그래서 경로 배정은 안정해야 한다. 즉 배정이 끝난 뒤 나머지 운전자가 배정받은 경로를 그대로 지킬 때, 어떤 운전자도 혼자 경로를 바꿔서 자기 요금을 줄일 수 없어야 한다. 어떤 운전자가 경로 $P$에서 경로 $Q$로 옮기면 차량 수도 함께 바뀐다. $Q$에 있고 $P$에는 없는 도로는 차량이 한 대 늘고, $P$에 있고 $Q$에는 없는 도로는 한 대 줄며, 그 운전자는 $Q$에 속한 도로의 차량 수 중 최댓값의 제곱을 낸다.

하루가 시작될 때 스펀지밥의 프로그램은 그날 Motel-Ghu에서 Tehran으로 가는 차량 수 $C$를 정확히 예측한다. 안정한 배정은 여러 가지일 수 있고, Rahyab은 그중 전체 차량이 내는 요금의 합이 가장 작은 배정을 쓴다. 도로 지도와 $C$가 주어질 때 그 합을 구하라.

입력은 여러 테스트 케이스로 이루어진다. 각 테스트 케이스의 첫 줄에는 공백으로 구분된 정수 $N$, $E$, $M$, $T$, $C$가 주어진다. $N$은 도시의 수, $E$는 도로의 수다 ($2 \le N \le 500$, $0 \le E \le 100000$). 도시에는 1번부터 $N$번까지 번호가 붙어 있다. $M$은 Motel-Ghu의 번호, $T$는 Tehran의 번호다 ($1 \le M, T \le N$, $M \ne T$). $C$는 금요일에 Motel-Ghu에서 Tehran으로 가는 차량 수다 ($0 \le C \le 10^6$). 이어지는 $E$개 줄에는 공백으로 구분된 정수 $x_i$와 $y_i$가 주어지며 ($1 \le x_i, y_i \le N$), 도시 $x_i$에서 도시 $y_i$로 가는 일방통행 도로를 뜻한다. 같은 두 도시를 같은 방향으로 잇는 도로가 여럿일 수 있고, 이때 각각은 차량 수를 따로 세는 별개의 도로다. Motel-Ghu에서 Tehran으로 가는 경로는 적어도 하나 있다. 입력의 마지막 줄에는 0이 다섯 개 주어지며, 이 줄은 테스트 케이스가 아니다.

각 테스트 케이스마다 요금의 합이 가장 작은 안정한 배정에서 전체 차량이 내는 요금의 합을 한 줄에 출력한다.