#include <bits/stdc++.h>
using namespace std;
int n, m;
int can[515];//判断状态i自己是否成立
int need[515];//判断状态i需要多少个棋子
long long f[10][515][82];

int main() {
	cin >> n >> m;
	int N = (1 << n) - 1;
	for (int i = 0; i <= N; i++) {
		int t = i;
		while (t) {
			if (t % 2 == 1)
				need[i]++;
			t /= 2;
		}
		if ((i & (i >> 1)) == 0 && (i & (i << 1)) == 0 )
			can[i] = 1;
	}

	for (int i = 0; i <= N; i++) {
		if (can[i] == 1) {
			f[1][i][need[i]] = 1;
		}
	}
	//先遍历行
	for (int i = 2; i <= n; i++) {
		//枚举当前行的状态
		for (int j = 0; j <= N; j++) {
			if (can[j] == 0)
				continue;
			//枚举上一行的状态
			for (int s = 0; s <= N; s++) {
				if (can[s] == 0)
					continue;
				if ((j & s) != 0)
					continue;
				if ((j & (s << 1)) != 0)
					continue;
				if ((j & (s >> 1)) != 0)
					continue;
				//枚举棋子总数
				for (int k = m; k >= need[j]; k--) {
					f[i][j][k] += f[i - 1][s][k - need[j]];
				}
			}
		}
	}
	long long res = 0;
	for (int i = 0; i <= N; i++) {
		res += f[n][i][m];
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, m, can[101][1025], need[1025];
int mat[105];
int f[101][1025][1025];

int main() {
	cin >> n >> m;
	for (int i = 1; i <= n; i++) {
		for (int j = 1; j <= m; j++) {
			char ch;
			cin >> ch;
			if (ch == 'P')
				mat[i] = mat[i] = (mat[i] << 1) | 1;
			else
				mat[i] = (mat[i] << 1);
		}
	}
	int N = (1 << m) - 1;
	for (int i = 0; i <= N; i++) {
		int t = i;
		while (t) {
			if (t % 2 == 1)
				need[i]++;
			t /= 2;
		}
	}
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j <= N; j++) {
			if ((j & (j >> 1)) != 0 || (j & (j >> 2)) != 0)
				continue;
			if ((j & (j << 1)) != 0 || (j & (j << 2)) != 0)
				continue;
			if ((mat[i] | j) != mat[i])
				continue;
			can[i][j] = 1;
		}
	}
	int res = 0;
	for(int i=0;i<=N;i++){
		if(can[1][i])res = max(res,need[i]);
	}
	for (int i = 0; i <= N; i++) {
		if (can[1][i] == 0)
			continue;
		for (int j = 0; j <= N; j++) {
			if (can[2][j] == 0)
				continue;
			if ((i & j) != 0)
				continue;
			f[2][j][i] = need[i] + need[j];
			res = max(res,f[2][j][i]);
		}
	}
	for (int i = 3; i <= n; i++) {
		//枚举第i行的状态
		for (int j = 0; j <= N; j++) {
			if (can[i][j] == 0)
				continue;
			//枚举第i-1行的状态
			for (int k = 0; k <= N; k++) {
				if (can[i - 1][k] == 0)
					continue;
				if ((j & k) != 0)
					continue;
				for (int s = 0; s <= N; s++) {
					if (can[i - 2][s] == 0)
						continue;
					if ((s & k) != 0 || (s & j) != 0)
						continue;
					f[i][j][k] = max(f[i][j][k], f[i - 1][k][s] + need[j]);
					res = max(res, f[i][j][k]);
				}
			}
		}
	}
	cout << res << endl;
	return 0;
}

#include <bits/stdc++.h>
using namespace std;
int n, w;
int f[100005], T[100005], W[100005], tim[100], weight[100];

int main() {
	cin >> w >> n;
	memset(f, 0x3f, sizeof(f));
	f[0] = 0;
	for (int i = 1; i <= n; i++) {
		cin >> tim[i] >> weight[i];
	}
	int N = (1 << n) - 1;
	for (int i = 0; i <= N; i++) {
		for (int j = 1; j <= n; j++) {
			if ((i & (1 << (j - 1))) == 0)
				continue;
			T[i] = max(T[i], tim[j]);
			W[i] += weight[j];
		}
	}
	for (int i = 0; i <= N; i++) {
		for (int j = i; ; j = i & (j - 1)) {
			if (W[i ^ j] <= w) {
				f[i] = min(f[i], f[j] + T[i ^ j]);
			}
			if (j == 0)
				break;
		}
	}
	cout << f[N] << endl;
	return 0;
}