p02179 Monster Buster_32110
problem

AOR Ika is a monster buster.
One day, as I was walking down the road, I met a sleeping monster.

AOR Ika, who has a strong fighting spirit, decides to hit the monster with a wake-up blow. However, the current attack power of AOR Ika is $ 0 $, and she cannot make a decent attack as it is.

AOR Ika-chan, who is devoting himself to the monster buster, was actually entrusted with a special whistle by his master. When he plays a specific song with this whistle, his attack power increases for a certain period of time.

Trained AOR Ika can play $ N $ songs. The $ i $ th song takes $ R_i $ seconds to play, and the attack power increases by $ A_i $ after the performance ends. After $ T_i $ seconds, the effect of this performance will be cut off and the attack power will return to that before the performance.

Also, AOR Ika-chan can play over and over. If you finish playing the same song during the effect time of the performance, the attack power will increase by $ W_i $ instead of $ A_i $. The time is not extended. Therefore, when the first effect of the $ i $ th song currently in effect expires, all the effects of the layered performance also expire.

Output the maximum attack power of AOR Ika-chan. No matter how much you play, no monster will occur, and AOR Ika-chan can attack in $ 0.5 $ seconds.



output

Output the maximum value of AOR Ika-chan's attack power. Also, output a line break at the end.

Example

Input

2
5 10 5 5
4 4 2 2


Output

14
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<ll, ll> l_l;
typedef pair<l_l, l_l> llll;
typedef pair<int, int> i_i;
template<class T>
inline bool chmax(T &a, T b) {
    if(a < b) {
        a = b;
        return true;
    }
    return false;
}

template<class T>
inline bool chmin(T &a, T b) {
    if(a > b) {
        a = b;
        return true;
    }
    return false;
}

//const ll mod = 1000000007;
const ll INF = 1e17;
ll N;
ll R[2005], A[2005], W[2005], T[2005];
ll Prev[4005];
ll Next[4005];
ll Next2[4005];
vector<llll> v;

int main() {
    //cout.precision(10);
    cin.tie(0);
    ios::sync_with_stdio(false);
    cin >> N;
    v.resize(N);
    for(int i = 0; i < N; i++) {
        cin >> v[i].second.second >> v[i].second.first >> v[i].first.second >> v[i].first.first;
        v[i].first.first += v[i].second.second;
    }
    sort(v.begin(), v.end());
    for(int i = 0; i < N; i++) {
        v[i].first.first -= v[i].second.second;
        R[i+1] = v[i].second.second;
        A[i+1] = v[i].second.first;
        W[i+1] = v[i].first.second;
        T[i+1] = v[i].first.first;
    }
    //for(int i = 0; i <= 4000; i++) Prev[i] = -INF;
    Prev[1] = 0;
    for(int song = 1; song <= N; song++) {
        for(int j = 0; j <= 4000; j++) {
            Next[j] = -INF;
            Next2[j] = -INF;
        }
        for(int j = 1; j <= 4000; j++) {
            if(j - 2 * R[song] >= 1 && j - R[song] <= T[song]) Next[j] = Prev[j - 2 * R[song]] + W[song] + A[song];
            else Next[j] = -INF;
        }
        for(int j = 1; j <= 4000; j++) {
            if(j - R[song] >= 1 && j - R[song] <= T[song]) chmax(Next[j], Next[j - R[song]] + W[song]);
        }
        for(int j = 4000; j >= 0; j--) {
            if(j - R[song] >= 1 && j - R[song] <= T[song]) chmax(Prev[j], Prev[j - R[song]] + A[song]);
            chmax(Prev[j], Next[j]);
        }
    }
    ll ans = 0;
    for(int i = 0; i <= 4000; i++) {
        chmax(ans, Prev[i]);
    }
    cout << ans << endl;
    return 0;
}

