Problem: Training is indispensable for achieving good results at ICPC. Rabbit wants to win at ICPC, so he decided to practice today as well.

Today's training is to improve reflexes and memory by performing whac-a-mole many times. I want to hit the moles that come out one after another and get as many points as possible.

The places where moles may appear are lined up in a straight line, and the coordinates are determined by the distance from the reference point. As the rabbit continued his training for a while, he noticed that the place and time when the moles appeared were always the same. Rabbit decided to record all the information and analyze it with a computer.

In order to hit the mole, after moving the hand to the position where the mole appears, it is necessary to hit the mole exactly at the timing when the mole appears. If you hit the mole well, you can get points according to the mole. The action of hitting the mole can be done in an instant, but there is a limit to the speed at which the hand can be moved. Rabbits can use both their left and right hands to hit the moles. The left and right hands can be moved independently, but the left hand must always be in a position with smaller coordinates than the right hand. I would like to find out how many points can be obtained at the maximum under such conditions.



Input


NV X Left X Right
X1 T1 P1
...
XN TN PN


N is the number of moles that come out, V is the maximum speed at which the hand can be moved, and XLeft and XRight are the coordinates of the initial positions of the left and right hands, respectively. Xi, Ti, and Pi are the coordinates of the position where the mole appears, the time from the start of the game to the appearance, and the points obtained when hitting, respectively.

1 ≤ N ≤ 3,000, 1 ≤ V ≤ 10,000, 1 ≤ XLeft <XRight ≤ 100,000, 1 ≤ X1 ≤ X2 ≤ ... ≤ XN ≤ 100,000, 1 ≤ Ti ≤ 100,000, 1 ≤ Pi ≤ 100,000. The same set as (Xi, Ti) does not appear multiple times.

Output

Output the maximum point at which the rabbit can be obtained on one line.

Examples

Input

3 10 150 250
100 20 123
201 10 67
202 10 45


Output

190


Input

1 7 20 90
55 5 73


Output

73


Input

10 2 1000 2000
400 300 1
600 200 1
700 800 1
700 500 1
900 600 1
1000 700 1
1300 900 1
1400 400 1
1500 1000 1
2000 100 1


Output

10

Solution (in CPP):

Solution:
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>
#include <iomanip>
#include <fstream>
#include <bitset>

using namespace std;

#define foreach(it, c) for (__typeof__((c).begin()) it=(c).begin(); it != (c).end(); ++it)
template <typename T> void print_container(ostream& os, const T& c) { const char* _s = " "; if (!c.empty()) { __typeof__(c.begin()) last = --c.end(); foreach (it, c) { os << *it; if (it != last) os << _s; } } }
template <typename T> ostream& operator<<(ostream& os, const vector<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const set<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const multiset<T>& c) { print_container(os, c); return os; }
template <typename T> ostream& operator<<(ostream& os, const deque<T>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const map<T, U>& c) { print_container(os, c); return os; }
template <typename T, typename U> ostream& operator<<(ostream& os, const pair<T, U>& p) { os << "(" << p.first << ", " << p.second << ")"; return os; }

template <typename T> void print(T a, int n, const string& split = " ") { for (int i = 0; i < n; i++) { cout << a[i]; if (i + 1 != n) cout << split; } cout << endl; }
template <typename T> void print2d(T a, int w, int h, int width = -1, int br = 0) { for (int i = 0; i < h; ++i) { for (int j = 0; j < w; ++j) { if (width != -1) cout.width(width); cout << a[i][j] << ' '; } cout << endl; } while (br--) cout << endl; }
template <typename T> void input(T& a, int n) { for (int i = 0; i < n; ++i) cin >> a[i]; }
#define dump(v) (cerr << #v << ": " << v << endl)

#define rep(i, n) for (int i = 0; i < (int)(n); ++i)
#define erep(i, n) for (int i = 0; i <= (int)(n); ++i)
#define all(a) (a).begin(), (a).end()
#define rall(a) (a).rbegin(), (a).rend()
#define clr(a, x) memset(a, x, sizeof(a))
#define sz(a) ((int)(a).size())
#define mp(a, b) make_pair(a, b)
#define ten(n) ((long long)(1e##n))

template <typename T, typename U> void upmin(T& a, const U& b) { a = min<T>(a, b); }
template <typename T, typename U> void upmax(T& a, const U& b) { a = max<T>(a, b); }
template <typename T> void uniq(T& a) { sort(a.begin(), a.end()); a.erase(unique(a.begin(), a.end()), a.end()); }
template <class T> string to_s(const T& a) { ostringstream os; os << a; return os.str(); }
template <class T> T to_T(const string& s) { istringstream is(s); T res; is >> res; return res; }
void fast_io() { cin.tie(0); ios::sync_with_stdio(false); }
bool in_rect(int x, int y, int w, int h) { return 0 <= x && x < w && 0 <= y && y < h; }

typedef long long ll;
typedef pair<int, int> pint;

const int dx[] = { 0, 1, 0, -1 };
const int dy[] = { 1, 0, -1, 0 };



template <typename FLOW, typename COST>
class PrimalDual
{
private:
    struct PrimalDualEdge
    {
        int to;
        FLOW cap;
        COST cost;
        int rev;
        PrimalDualEdge(int to, FLOW cap, COST cost, int rev)
            : to(to), cap(cap), cost(cost), rev(rev) { }
    };
public:
    int V;
    vector<vector<PrimalDualEdge> > g;

    PrimalDual(int V) : V(V), g(V) { }

    void add_edge(int from, int to, FLOW cap, COST cost)
    {
        g[from].push_back(PrimalDualEdge(to, cap, cost, g[to].size()));
        g[to].push_back(PrimalDualEdge(from, 0, -cost, g[from].size() - 1));
    }
    void add_undirected(int a, int b, FLOW cap, COST cost)
    {
        add_edge(a, b, cap, cost);
        add_edge(b, a, cap, cost);
    }

    COST min_cost_flow(int s, int t, FLOW f)
    {
        vector<COST> h(V);
        COST res = 0;
        int _f = f;
        while (_f > 0)
        {
            typedef pair<COST, int> _p;
            const COST _INF = (COST)((1LL << 60) | (1 << 29));
            priority_queue<_p, vector<_p>, greater<_p> > q;
            vector<COST> dis(V, _INF);
            vector<int> prevv(V), preve(V);
            dis[s] = 0;
            q.push(_p(0, s));
            while (!q.empty())
            {
                _p p = q.top(); q.pop();
                int v = p.second;
                COST cost = p.first;
                if (cost > dis[v])
                    continue;

                for (int i = 0; i < g[v].size(); ++i)
                {
                    PrimalDualEdge& e = g[v][i];
                    const COST _eps = 1e-10;
                    COST c = cost + e.cost + h[v] - h[e.to];
                    if (e.cap > 0 && c + _eps < dis[e.to])
                    {
                        dis[e.to] = c;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        q.push(_p(c, e.to));
                    }
                }
            }

            if (dis[t] == _INF)
            {
                // cant flow _f
                return _INF;
            }

            for (int i = 0; i < V; ++i)
                h[i] += dis[i];

            FLOW d = _f;
            for (int i = t; i != s; i = prevv[i])
                d = min(d, g[prevv[i]][preve[i]].cap);
            _f -= d;
            res += d * h[t];
            for (int i = t; i != s; i = prevv[i])
            {
                PrimalDualEdge& e = g[prevv[i]][preve[i]];
                e.cap -= d;
                g[e.to][e.rev].cap += d;
            }
        }

        return res;
    }

    COST min_cost_flow_spfa(int s, int t, FLOW f)
    {
        COST res = 0;
        int _f = f;
        while (_f > 0)
        {
            const COST _INF = (COST)((1LL << 60) | (1 << 29));
            vector<COST> dis(V, _INF);
            vector<int> prevv(V), preve(V);

            vector<bool> in_q(V);
//             queue<int> q;
            priority_queue<int, vector<int>, greater<int>> q;
            dis[s] = 0;
            q.push(s);
            in_q[s] = true;

            while (!q.empty())
            {
                int v = q.top(); q.pop();
//                 int v = q.front(); q.pop();
                COST cost = dis[v];
                in_q[v] = false;

                for (int i = 0; i < g[v].size(); ++i)
                {
                    PrimalDualEdge& e = g[v][i];
                    const COST _eps = 1e-10;
                    COST c = cost + e.cost;
                    if (e.cap > 0 && c + _eps < dis[e.to])
                    {
                        dis[e.to] = c;
                        prevv[e.to] = v;
                        preve[e.to] = i;
                        if (!in_q[e.to])
                        {
                            q.push(e.to);
                            in_q[e.to] = true;
                        }
                    }
                }
            }

            if (dis[t] == _INF)
            {
                // cant flow _f
                return _INF;
            }

            FLOW d = _f;
            for (int i = t; i != s; i = prevv[i])
                d = min(d, g[prevv[i]][preve[i]].cap);
            _f -= d;
            res += d * dis[t];
            for (int i = t; i != s; i = prevv[i])
            {
                PrimalDualEdge& e = g[prevv[i]][preve[i]];
                e.cap -= d;
                g[e.to][e.rev].cap += d;
            }
        }

        return res;
    }
};
int n;
int in(int i) { return 1 + 2 * i; }
int out(int i) { return in(i) + 1; }
int main()
{
    fast_io();

    int x_left, x_right;
    ll v;
    cin >> n >> v >> x_left >> x_right;

    int x[3333], t[3333], p[3333];
    vector<pair<int, pint>> a;
    rep(i, n)
    {
        cin >> x[i] >> t[i] >> p[i];
        a.push_back(make_pair(t[i], pint(x[i], p[i])));
    }
    sort(all(a));
    rep(i, n)
    {
        t[i] = a[i].first;
        x[i] = a[i].second.first;
        p[i] = a[i].second.second;
    }

    PrimalDual<int, int> pd(2 * n + 2 + 2);
    int src = 0;
//     int in = 1;
//     int out = in + n;
//     int left = out + n;
    int left = 1 + 2 * n;
    int right = left + 1;
    int sink = right + 1;

    pd.add_edge(src, sink, 2, 0);
    pd.add_edge(src, left, 1, 0);
    pd.add_edge(src, right, 1, 0);
    rep(i, n)
    {
        pd.add_edge(in(i), out(i), 1, -p[i]);
        pd.add_edge(out(i), sink, 1, 0);

        if (abs(x[i] - x_left) <= v * t[i])
            pd.add_edge(left, in(i), 1, 0);
        if (abs(x[i] - x_right) <= v * t[i])
            pd.add_edge(right, in(i), 1, 0);

        rep(j, n)
        {
            if (t[i] < t[j])
            {
                if (abs(x[j] - x[i]) <= v * (t[j] - t[i]))
                    pd.add_edge(out(i), in(j), 1, 0);
            }
        }
    }

    int mcf = pd.min_cost_flow_spfa(src, sink, 2);
    assert(mcf <= 0);
    cout << -mcf << endl;
}