1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
#include <cstdio>
#include <queue>
using namespace std;

int n,m,k;
unsigned long long int a[1000002];
unsigned long long int b[1000002];
char c[2002][2002];
char tmp;

int main() {
	scanf("%d %d %d\n", &n, &m, &k);
	for(int i = 1; i<=n;i++) {
		for(int j = 1; j<=m; j++) {
			scanf("%c", &c[i][j]);
		}
		scanf("%c", &tmp);
	}

	for (int i = 0; i < k; ++i)
	{
		scanf("%llu %llu", &a[i], &b[i]);
	}

	for (int j=0; j<=m; j++) c[0][j] = c[n+1][j] = 'X';
	for (int i = 0; i <=n + 1; ++i) c[i][0] = c[i][m+1] = 'X';

	m++;
	n++;

	// printf("  ");
	// for(int j = 0; j<=m+1; j++) {
	// 	printf("%d",j);
	// }printf("\n");
	// for(int i = 0; i<=n+1;i++) {
	// 	printf("%d:", i);
	// 	for(int j = 0; j<=m+1; j++) {
	// 		printf("%c", c[i][j]);
	// 	}
	// 	printf("\n");
	// }

	// BFS
	c[1][1] = 'S';
	queue<int> q;
	q.push (m + 1);

	while(!q.empty()) {
		int idx = q.front();
		q.pop();

		int i = idx / m;
		int j = idx % m;
		if (i == n-1 && j==m-1) {
			break;
		}

		if(c[i+1][j] == '.') {
			c[i+1][j] = 'U';
			q.push(m*(i+1) + j);
		} 
		if(c[i-1][j] == '.') {
			c[i-1][j] = 'D';
			q.push(m*(i-1) + j);
		} 
		if(c[i][j+1] == '.') {
			c[i][j+1] = 'L';
			q.push(m*i + j+1);
		}
		if(c[i][j-1] == '.') {
			c[i][j-1] = 'R';
			q.push(m*i + j-1);
		}
	}

	// printf("  ");
	// for(int j = 0; j<=m+1; j++) {
	// 	printf("%d",j);
	// }printf("\n");
	// for(int i = 0; i<=n+1;i++) {
	// 	printf("%d:", i);
	// 	for(int j = 0; j<=m+1; j++) {
	// 		printf("%c", c[i][j]);
	// 	}
	// 	printf("\n");
	// }

	// restore path
	unsigned long long int ups = 0, downs = 0;

	int i = n-1;
	int j = m-1;


	while(c[i][j] != 'S') {
		char s = c[i][j];
		if(s == 'U' || s == 'L') {
			ups++;
		} else {
			downs++;
		}
		if (s == 'U') i--;
		else if (s == 'D') i++;
		else if (s == 'L') j--;
		else j++;
	}

	// printf("ups %d downs %d\n", ups, downs);
	for (int i = 0; i < k; ++i) {
		a[i] = (a[i] * ups) + (b[i] * downs);
	}

	int min_count = 1;
	unsigned long long int min = a[0]; 
	for (int i = 1; i < k; ++i) {
		if( a[i] < min) {
			min = a[i];
			min_count = 1;
		} else if (a[i] == min) {
			min_count++;
		}
	}
	printf("%llu %d\n", min, min_count);


}