Autores: Mauricio Cari, Gabriel Carmona, Benjamín Letelier

Tiempo límite: 2 segundos

Memoria límite: 256 megabytes

Como era de esperar, Cristina Ruiz seleccionó nuevamente a Coquimbo como sede del ICPC. En esta ocasión, el contest poseerá \(K+ 1\) problemas, cada uno escrito por un autor diferente. Para asegurarse que los problemas no fueran filtrados, decidió instaurar una sencilla medida que aplicará a cada autor de un problema: encerrarlo en una casa con un computador sin internet. Felizmente, Cristina encontró un hermoso vecindario que cumple con estos requisitos.

El vecindario puede verse como un grafo ponderado simple y conexo con \(N\) casas y \(M\) calles, y para cada calle Cristina sabe cuántos minutos se demora en recorrerla. Ella también sabe que el computador ubicado en la \(i\)-ésima casa se demora \(C_{i}\) minutos en subir un archivo a su USB. Actualmente, \(K\) autores ya se encuentran posicionados en sus respectivas casas trabajando en sus problemas, pero a Cristina aún le falta decidir en cuál de las \(S\) posibles casas desocupadas colocar al autor encargado del \(I\)-ésimo problema de la competencia.

Lo que sí sabe es que su ruta consistirá en entrar a las casas en el mismo orden en el que los problemas serán presentados en la competencia. Luego, dentro de una casa, subirá el archivo del problema a su USB e irá a la siguiente casa. Su ruta comenzará en la casa del autor del primer problema, y terminará luego de almacenar el último problema en su USB. Obviamente, esto lo quiere hacer lo más rápido posible.

¿En cuál de las posibles \(S\) casas desocupadas se debe colocar al autor del \(I\)-ésimo problema para minimizar el tiempo de ruta de Cristina?

Entrada

La primera línea contiene los enteros \(N\), \(M\), \(K\), \(I\), \(S ―\) el número de casas, el número de calles, el número de autores ya ubicados, el índice del problema del autor a ser colocado y el número de posibles casas para colocar al autor (\(N\cdot (K+ 1) \le 10^{5}\), \(M\cdot (K+ 1) \le 10^{6}\), \(1 \le I\le (K+ 1)\), \(2 \le S\le (N-K)\)).

Cada una de las siguientes \(M\) líneas poseen una arista ponderada bidireccional de la forma \((u, v, d)\), indicando que existe una calle entre las casas \(u\) y \(v\) que Cristina tarda \(d\) minutos en recorrer (\(1 \le u, v\le\) \(N\), \(1 \le d\le 10^{9}\)).

La siguiente línea poseerá \(N\) enteros, donde la \(i\)-ésima posición corresponde a \(C_{i} ―\) la cantidad de minutos que demora el computador de la casa \(i\) en subir un archivo al USB de Cristina (\(1 \le C_{i}\le 10^{9}\)).

La siguiente línea posee \(K+ 1\) enteros diferentes, donde el \(i\)-ésimo entero \(k_{i}\) indica la casa donde se encuentra el autor del problema \(i\) (\(1 \le k_{i}\le N\), \(k_{I}= -1\) ).

La última línea posee \(S\) enteros diferentes, donde el \(i\)-ésimo entero \(s_{i}\), indica una casa desocupada que puede ser elegida para colocar al autor del \(I\)-ésimo problema (\(1 \le s_{i}\le N\)).

Salida

Imprime un único número, indicando la posición de la casa desocupada a eligir que minimice el tiempo de ruta de Cristina. Si existen múltiples soluciones, imprime la casa con menor posición entre estas.

Entrada 1

6 7 2 2 4
1 2 1
2 6 2
2 3 4
3 5 2
6 3 1
6 5 5
5 4 3
1 4 2 4 5 1
2 -1 5
1 3 4 6

Salida 1

6

Entrada 2

6 7 2 1 4
1 2 1
2 6 2
2 3 4
3 5 2
6 3 1
6 5 5
5 4 3
1 4 2 4 5 1
-1 2 5
1 3 4 6

Salida 2

1

Nota

• En el primer ejemplo, si colocamos al autor en la casa 6, el mejor tiempo de ruta de Cristina es de 15 minutos, el cuál es el mínimo posible a obtener entre las posibles opciones.