京东（算法岗0917）

const int len = 10005;
vector<int> infor(len, 0);
int N, V, v, w, s;


int main() {
	cin >> N >> V;
	for (int i = 0; i < N; i++) {
		cin >> s >> v >> w;
		for (int j = V; j >= 0; --j) {
			for (int k = 1; k <= s && k*v <= j; ++k) {
				infor[j] = max(infor[j], infor[j - k * v] + k*w);
			}
		}
	}
	cout << infor[V];

	getchar();
	return 0;
}

void dfs(vector<vector<char>>& mat, int i, int j) {
	if (i < 0 || i >= mat.size() || j < 0 || j >= mat[0].size() || mat[i][j] == '#' || mat[i][j] == '*')
		return;
	mat[i][j] = '*';
	dfs(mat, i + 1, j);
	dfs(mat, i - 1, j);
	dfs(mat, i, j + 1);
	dfs(mat, i, j - 1);
}


int main() {

	int t, n, m;
	cin >> t;
	for (int i = 0; i < t; i++) {
		cin >> n >> m;
		int start_x = -1, start_y = -1, end_x = -1, end_y = -1;
		vector<vector<char>> mat(n, vector<char>(m));
		for (int i = 0; i < n; i++) {
			for (int j = 0; j < m; j++) {
				char tmp;
				cin >> tmp;
				if (tmp == 'E') {
					end_x = i;
					end_y = j;
				}
				if (tmp == 'S') {
					start_x = i;
					start_y = j;
				}
				mat[i][j] = tmp;
			}
		}
		dfs(mat, start_x, start_y);
		if (mat[end_x][end_y] == '*')
			cout << "YES" << endl;
		else
			cout << "NO" << endl;
	}

	getchar();
	return 0;
}