SPOJ Brasil

Jean é um caixeiro viajante. Ele sempre está viajando entre uma cidade e outra. Quando ele chega em uma cidade, ele vende tudo que ele tem e compra coisas novas. Então, ele viaja para outra cidade, vende suas coisas e compra outras novas.

Neste problema, você deverá encontrar a quantidade total de dinheiro que Jean ganhará em uma jornada. Em uma jornada, ele pode ir para uma cidade mais de uma vez e ele deve terminar a jornada em alguma cidade da lista de cidades finais. Existe também uma cidade inicial para sua jornada e um número de viagens entre duas cidades que Jean deseja fazer durante a sua jornada.

Entrada

O arquivo de entrada contém vários conjuntos de entrada. A descrição de cada conjunto é dada a seguir:

Cada conjunto começa com quatro inteiros: C (2 ≤ C ≤ 100), o número de cidades, S (1 ≤ S ≤ 100), o identificador da cidade de início, E (1 ≤ E ≤ 100), o número de cidades nas quais a jornada pode terminar, e T (1 ≤ T ≤ 1000), o número de viagens entre duas cidades que Jean quer fazer.

Seguem C linhas com C inteiros não-negativos. O j-ésimo inteiro da i-ésima linha descreverá o lucro que Jean tem quando ele vai da cidade i para a cidade j. Como ele não quer fazer uma viagem para a cidade na qual ele já está, o i-ésimo inteiro da i-ésima linha sempre será 0. Note que ir da cidade i para a cidade j pode ocasionar um lucro diferente daquele de ir da cidade j para a cidade i.

Por fim, haverá uma linha com E inteiros, representando os identificadores das cidades nas quais Jean pode terminar a sua jornada.

A entrada é terminada por um conjunto onde C=S=E=T=0. Este conjunto não deve ser processado. Há uma linha em branco entre dois conjuntos de entrada.

Saída

Para cada conjunto de entrada produza uma linha de saída, o lucro total que Jean pode obter na jornada correspondente.

Exemplo

Entrada:
3 1 2 2
0 3 5
5 0 1
9 2 0
2 3

0 0 0 0

Saída:
7