[문제요약] Last week Mister George visited Croatia. 지난주 게오르게씨가 크로아티아를 방문했다. Since Mister George is a very important person, while he was in a street, the police disallowed entry to that street, but vehicles that entered the street before Mister George could continue driving. 그는 VIP 이기때문에 그가 진입한 도로는 보안상의 이유로 진입을 허가하지 않는다. 하지만 이미 진입한 차량에 대해서 는 운행을 허가 한다.

While Mister George was visiting, Luka drove his truck around town. 게오르게씨가 방문하는 동안 루카는 그의 시내에서 그의 트럭으로 운행하고 있었다. But because of some of the streets being closed off, he couldn't make his delivery in time and almost lost his job. 그러나 어떤 도로는 봉쇄되었기에 그는 시간내에 물건을 배달할수가 없어 거의 일자리를 잃을 수도 이다. Although it is late now, he is wondering how he could have planned his delivery better 지금 늦었지만 그는 배달 할 수 있는 더 좋은 방법을 찾고 있다. i.e. what would have been the least time needed to make his delivery while Mister George was visiting. 즉 He knows the route mister George took.

The city is modeled with intersections and two-way streets connecting them. For each street, Luka knows how much time he needs to traverse it (mister George needs the same amount of time). For example, if Mister George starts traversing a street during minute 10 and needs 5 minutes to exit it, this street will be blocked during minutes 10, 11, 12, 13 and 14. Luka can enter the street during minutes 9 and earlier, or 15 and later.

Write a program that calculates the least amount of time Luka needs to make his delivery, if he starts driving K minutes after the arrival of Mister George.

While Mister George was visiting, Luka drove his truck around town. But because of some of the streets being closed off, he couldn't make his delivery in time and almost lost his job. Although it is late now, he is wondering how he could have planned his delivery better i.e. what would have been the least time needed to make his delivery while Mister George was visiting. He knows the route mister George took.

The city is modeled with intersections and two-way streets connecting them. For each street, Luka knows how much time he needs to traverse it (mister George needs the same amount of time). For example, if Mister George starts traversing a street during minute 10 and needs 5 minutes to exit it, this street will be blocked during minutes 10, 11, 12, 13 and 14. Luka can enter the street during minutes 9 and earlier, or 15 and later.

Write a program that calculates the least amount of time Luka needs to make his delivery, if he starts driving K minutes after the arrival of Mister George.

입력

• The first line contains two integers N and M (2 ≤ N ≤ 1000, 2 ≤ M ≤ 10 000), the number of intersections and the number of streets. The intersections are numbered 1 to N.
• The second line contains four integers A, B, K and G (1 ≤ A, B ≤ N, 0 ≤ K ≤ 1000, 0 ≤ G ≤ 1000). These are, in order:
  • The intersection where Luka starts;
  • The intersection Luka must get to;
  • The difference in starting times between mister George and Luka (Luka starts at intersection A exactly K minutes after mister George starts his route);
  • The number of intersections on Mister George's route.
• The third line contains G integers, the labels of intersections mister George will visit. Every pair of adjacent integers denotes a street he will traverse. That street will exist and Mister George will traverse every street at most once.

출력

입출력 예

input 

6 5 
1 6 20 4 
5 3 2 4 
1 2 2 
2 3 8 
2 4 3 
3 6 10 
3 5 15 

output 

21 

input 

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

output 

40 

출처:coci 2007-2008 contest6 4/6