// #include <bits/stdc++.h> #include <iostream> #include <cmath> #include <algorithm> #include <map> #include <vector> #include <iomanip> #include <string> #include <queue> #include <set> #include <deque> #include <numeric> #include <stack> #include <chrono> using namespace std; void fast_io(){ // freopen("", "r", stdin); // freopen("", "w", stdout); ios::sync_with_stdio(0); cin.tie(); cout.tie(); cout << setprecision(9); } #define int long long #define endl '\n' #define all(v) (v).begin(), (v).end() #define rall(v) (v).rbegin(), (v).rend() #define fi first #define se second const int N = 4e2; bool dp[N][N][N]; void solve() { int n, K; cin >> n >> K; string s; cin >> s; s = "." + s; int pref[n + 1] = {}; for (int i = 1; i <= n; i++) pref[i] += pref[i - 1] + (s[i] == 'C'); for (int le = 1; le <= n; le++){ for (int l = 1; l + le - 1 <= n; l++){ int r = l + le - 1; for (int x = 0; x < K; x++){ int y = pref[n] - pref[r] + pref[l - 1] - x; if (y >= K){ dp[l][r][x] = 1; continue; } bool b1 = (l == r or dp[l + 1][r][y] == 0); bool b2 = (l == r or dp[l][r - 1][y] == 0); if (x < K - (s[l] == 'C') && b1){ dp[l][r][x] = 1; } if (x < K - (s[r] == 'C') && b2){ dp[l][r][x] = 1; } } } } cout << (dp[1][n][0] ? "DA" : "NE") << endl; return; } signed main() { fast_io(); srand(chrono::steady_clock::now().time_since_epoch().count()); int tc = 1; // cin >> tc; while (tc--) solve(); return 0; }