Ignacio is un chico de la facultad 3 que es realmente malo jugando Dark Souls. Dark Souls es un juego de rol, donde cada jugador adquiere cierta cantidad de almas por cada enemigo derrotado, y con esas almas cada jugador puede comprar items, entre otras cosas. Ignacio actualmente está jugando en línea con sus amigos un nuevo DLC del juego llamado The UCI Quest. La compañía Fromsoftware anunció que el primer jugador que alcance cierta cantidad de almas, ganará como premio una camiseta de Cristiano Ronaldo, el mayor ídolo de Ignacio.

Como Ignacio no es un jugador muy bueno, solicita tu ayuda. El problema es el siguiente: tienes un mapa del DLC, que está compuesto por regiones conectadas a través de pasillos. Las regiones están enumeradas desde 1 a N. Cada región tiene un número de almas asociadas (El proceso de matar todos los enemigos de la región). Pero todo no es tan fácil. Hay pasillos llenos de Basiliscos. Estas son criaturas que sueltan gas por la boca y te maldicen. Puedes ser maldito a lo máximo K veces en un juego. Como tú tienes mucho miedo a los Basiliscos, todo lo que puedes hacer es correr bien fuerte a través del pasillo hasta que alcances una región. Cada vez que pasas por un pasillo lleno de Basiliscos, el contador de maldiciones es incrementado en 1. Pero no todo son malas noticias. En tu inventario llevas exactamente un ítem llamado hueso de regreso(ítem de un solo uso).

El hueso de regreso te envía a la última hoguera donde descansaste, ubicada en una región específica. Cuando usas el hueso de regreso y descansas en una hoguera, todos los enemigos de las regiones vuelven a la vida, y puedes volver a recolectar esas almas. Pero esta hoguera es realmente extraña, y está bloqueada en una habitación con un mecanismo extraño que solo se abre desde dentro y desaparece junto a la hoguera en cuanto descanses, por lo que la única forma de descansar en dicha hoguera es usando el hueso de regreso. Ignacio quiere saber cuál es la mayor cantidad de almas que puede obtener, considerando que no puede ser maldito más de K veces en un juego.

ENTRADA

La primera línea contiene 5 números, N, M, B, S y K. (4 ≤ N ≤ 14, 3 ≤ M ≤ 91, 1 ≤ B ≤ N, 1 ≤ S ≤ N, 1 <= K <= M), el número de regiones en el DLC, el número de pasillos, el número de la región donde está ubicada la hoguera, la región donde comienzas a jugar y la cantidad máxima de maldiciones.
La próxima línea contiene N números A1 A2...An (1 ≤ Ai ≤ 1000000). Cada Ai representa la cantidad de almas de la región i (1 ≤ i ≤ N). Las próximas M líneas contienen tres enteros x, y y z (1 ≤ x, y ≤ N, 0 ≤ z ≤ 1). Significa que la región x está conectada con la región y por un pasillo. El valor de z indica si el pasillo está lleno de Basiliscos (z = 1) o libre de Basiliscos (z = 0).

SALIDA

La máxima cantidad de almas que es posible obtener visitando ciertas regiones y no siendo maldecido más de K veces.

EJEMPLO DE ENTRADA

4 3 1 1 1
50 50 50 1000000
1 2 1
2 3 0
3 4 1

SALIDA. 200