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
127
128
129
130
131
#include <bits/stdc++.h>

int main()
{
	std::ios_base::sync_with_stdio(0);
	
	int n, m, k;

	std::cin >> n >> m >> k;

	std::vector<std::string> map(n);

	std::cin.ignore(std::numeric_limits<std::streamsize>::max(), '\n');

	for(int i=0;i<n;i++)
	{
		std::getline(std::cin, map[i]);
	}

	std::vector<std::vector<int>> g(n, std::vector<int>(m,-1));

	std::queue<std::pair<int,int>> q;

	q.push(std::make_pair(0,0));

	int depth = 0;

	while(!q.empty())
	{
		auto v = q.front();
		q.pop();

		if(g[v.first][v.second] != -1) continue;

		g[v.first][v.second] = depth;

		if(v.first == n-1 && v.second == m-1)
		{
			break;
		}

		if(v.first-1 >=0 && map[v.first-1][v.second] == '.' && g[v.first-1][v.second] == -1)
		{
			q.emplace(v.first-1, v.second);
		}
		if(v.first < n-1 && map[v.first+1][v.second] == '.' && g[v.first+1][v.second] == -1)
		{
			q.emplace(v.first+1, v.second);
		}
		if(v.second-1 >=0 && map[v.first][v.second-1] == '.' && g[v.first][v.second-1] == -1)
		{
			q.emplace(v.first, v.second-1);
		}
		if(v.second < m-1 && map[v.first][v.second+1] == '.' && g[v.first][v.second+1] == -1)
		{
			q.emplace(v.first, v.second+1);
		}

		depth++;
	}
	
	std::pair<int,int> cur_pos = std::make_pair(n-1, m-1);

	int aa = 0, bb = 0;

	while(cur_pos != std::make_pair(0,0))
	{
		char dir = '-';

		const auto& v = cur_pos;

		std::pair<int,int> next_pos;

		int min = std::numeric_limits<int>::max();

		if(v.first-1 >=0 && g[v.first-1][v.second] != -1 && g[v.first-1][v.second] < min)
		{
			min = g[v.first-1][v.second];
			next_pos = std::make_pair(v.first-1, v.second);
			dir = 'd';
		}
		if(v.first < n-1 && g[v.first+1][v.second] != -1 && g[v.first+1][v.second] < min)
		{
			min = g[v.first+1][v.second];
			next_pos = std::make_pair(v.first+1, v.second);
			dir = 'u';
		}
		if(v.second-1 >=0 && g[v.first][v.second-1] != -1 && g[v.first][v.second-1] < min)
		{
			min = g[v.first][v.second-1];
			next_pos = std::make_pair(v.first, v.second-1);
			dir = 'r';
		}
		if(v.second < m-1 && g[v.first][v.second+1] != -1 && g[v.first][v.second+1] < min)
		{
			min = g[v.first][v.second+1];
			next_pos = std::make_pair(v.first, v.second+1);
			dir = 'l';
		}

		cur_pos = next_pos;

		if(dir == 'l' || dir == 'u')
		{
			bb++;
		}
		else
		{
			aa++;
		}
		
	}

	std::unordered_map<int,int> rr;

	int rmin = std::numeric_limits<int>::max();

	for(int i=0;i<k;i++)
	{
		int a, b;
		std::cin >> a >> b;

		int r = (aa*a) + (bb*b);
		rr[r]++;
		rmin = std::min(rmin,r);
	}

	std::cout << rmin << " " << rr[rmin] << "\n";

	return 0;
}