Problem G - Travelling Salesman

Time Limit: 1 second

Jean is a travelling salesman. He keeps travelling among some cities. When he arrives in a city, he sells everything he has and buy new things. Then he travels to another city, sells his items and buy new ones.

In this problem you will have to find the total amount of money Jean will gain on the optimal tour. On a tour he can go to some city more than once, and he must finish his tour in some cities. Also there is a starting city for his tour and the number of inter-city travels he wants to do in his tour.

Input

The input file contains several input sets. The description of each set is given below:

Each set starts with four integers C (2 ≤ C ≤ 100), the number of cities, S (1 ≤ S ≤ 100), the identifier of the starting city, E (1 ≤ E ≤ 100), the number of cities his tour can end at, and T (1 ≤ T ≤ 1000), the number of inter-city travels he wants to do.

Follow C lines with C non-negative integers. The j'th integer of the i'th line will describe the profit he earns when he goes from city i to city j. As he does not want to make a trip to a city he is already, the i'th integer of the i'th line will always be 0. Note that going from city i to city j can have a different profit than going from city j to city i.

After there will be a line with E integers, the identifier of the cities he can end his tour.

Input is terminated by a set where C=S=E=T=0. This set should not be processed. There is a blank line beteween two input sets.

Output

For each input set produce one line of output, the total profit he can earn in the corresponding tour.

Sample Input

3 1 2 2
0 3 5
5 0 1
9 2 0
2 3

0 0 0 0

Sample Input

7

#include <stdio.h>
#include <string.h>
typedef struct {
    int v[100][100];
}Matrix;
Matrix A, one, zero;
int max(int x, int y) {
	return x > y ? x : y;
}
Matrix multiply(Matrix *x, Matrix *y, int n) {
	static int i, j, k;
	static Matrix tmp;
	tmp = zero;
	for(i = 0; i < n; i++) {
		for(j = 0; j < n; j++) {
			for(k = 0; k < n; k++) {
				tmp.v[i][k] = max(x->v[i][j] + y->v[j][k], tmp.v[i][k]);
			}
		}
	}
	return tmp;
}
Matrix DandC(int n, int k) {
	Matrix x = zero, y = A;
	while(k) {
		if(k&1) {
			if(memcmp(&x, &zero, sizeof(x)) == 0)
				x = y;
			else
				x = multiply(&x, &y, n);
		}
		y = multiply(&y, &y, n);
		k >>= 1;
	}
	return x;
}
int main() {
	int C, S, E, T;
	int i, j;
	while(scanf("%d %d %d %d", &C, &S, &E, &T) == 4) {
		if(C == 0 && S == 0 && E == 0 && T == 0)
			break;
		memset(&A, 0, sizeof(Matrix));
		memset(&one, 0, sizeof(Matrix));
		memset(&zero, 0, sizeof(Matrix));
        for(i = 0; i < C; i++) 
			one.v[i][i] = 1;
		for(i = 0; i < C; i++)
			for(j = 0; j < C; j++)
				scanf("%d", &A.v[i][j]);
		Matrix result = DandC(C, T);
		int ed, best = 0;
		while(E--) {
			scanf("%d", &ed);
			if(best < result.v[S-1][ed-1])
				best = result.v[S-1][ed-1];
		}
		printf("%d\n", best);
	}
    return 0;
}