#include #include #include #include #include #include #include #include #define rep(i, a, b) for (int i = int(a); i < int(b); i++) using namespace std; using ll = long long int; // NOLINT using P = pair; // clang-format off #ifdef _DEBUG_ #define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; debug_print(__VA_ARGS__); } while(false) template void debug_print(const T &t, const Ts &...ts) { cerr << t; ((cerr << ", " << ts), ...); cerr << endl; } #else #define dump(...) do{ } while(false) #endif template vector make_v(size_t a, T b) { return vector(a, b); } template auto make_v(size_t a, Ts... ts) { return vector(a, make_v(ts...)); } template bool chmin(T &a, const T& b) { if (a > b) {a = b; return true; } return false; } template bool chmax(T &a, const T& b) { if (a < b) {a = b; return true; } return false; } template void print(const T& t, const Ts&... ts) { cout << t; ((cout << ' ' << ts), ...); cout << '\n'; } template void input(Ts&... ts) { (cin >> ... >> ts); } template istream &operator,(istream &in, T &t) { return in >> t; } struct Inf { template constexpr operator T() { return numeric_limits::max() / 2; } }; // clang-format on #include int popcount(ll bits) { bits = (bits & 0x5555555555555555LL) + (bits >> 1 & 0x5555555555555555LL); bits = (bits & 0x3333333333333333LL) + (bits >> 2 & 0x3333333333333333LL); bits = (bits & 0x0f0f0f0f0f0f0f0fLL) + (bits >> 4 & 0x0f0f0f0f0f0f0f0fLL); bits = (bits & 0x00ff00ff00ff00ffLL) + (bits >> 8 & 0x00ff00ff00ff00ffLL); bits = (bits & 0x0000ffff0000ffffLL) + (bits >> 16 & 0x0000ffff0000ffffLL); return (bits & 0x00000000ffffffffLL) + (bits >> 32 & 0x00000000ffffffffLL); } int main() { cin.tie(nullptr); ios::sync_with_stdio(false); int n, a, b; cin >> n >> a >> b; vector x(n), y(n), k(n); rep(i,0,n){ cin >> x[i] >> y[i] >> k[i]; } auto dist = [&](int i, int j) -> int { return abs(x[i] - x[j]) + abs(y[i] - y[j]); }; const int bits = 1 << n; auto dp = make_v(bits, n + 1, n + 1, false); rep(i,0,n){ dp[1 << i][n][i] = true; } rep(bit, 1, bits) { rep(i,0,n+1) { rep(j,0,n+1){ if (!dp[bit][i][j]) continue; rep(t,0,n) { if ((bit >> t) & 1) continue; int dist1 = dist(j, t); int pop = popcount(bit); bool ok = false; if (pop == 1 && a <= dist1) ok = true; int diff = abs(k[t] - k[j]); if (b <= diff) ok = true; if (i != n) { int dist2 = dist(t, j) + dist(t, i); if (a <= dist2) { ok = true; } } if (ok) { dp[bit | 1 << t][j][t] = true; } } } } } int ans = 0; rep(bit,0,bits) { rep(i,0,n+1){ rep(j,0,n+1) { if (dp[bit][i][j]) { chmax(ans, popcount(bit)); } } } } print(ans); return 0; }