Untitled

#include <iostream>

#include <limits>
#include <vector>
#include <map>
#include <set>
#include <cmath>
#include <algorithm>

typedef long long ll;

using namespace std;

typedef pair<ll, ll> pii;

ll N;

const int MAXN = 101;
const int MAXZ = 1e5+5;
ll X[MAXN], Y[MAXN], Z[MAXN];

const ll INF = 1e18;

// at pos, seat
ll dp[MAXN][MAXZ];

void solve() {
    cin>>N;

    for(int i=0; i<MAXN; i++) {
        for(int j=0; j<MAXZ; j++) {
            dp[i][j] = INF;
        }
    }

    ll t_seats = 0;
    // cost, reward
    vector<pii> arr;
    ll tot_seats = 0;
    for(int i=0; i<N; i++) {
        cin>>X[i]>>Y[i]>>Z[i];
        tot_seats += Z[i];

        if(X[i] > Y[i]) {
            t_seats += Z[i];
            // arr.push_back({0, Z[i]});
        } else {
            ll half =  (Y[i] + X[i] + 1 ) / 2;
            ll need = half - X[i];
            arr.push_back({need, Z[i]});
        }
    }

    ll need_seats = max(0LL, ((tot_seats + 1) / 2) - t_seats);

    // ll need_seats = (tot_seats + 1) / 2;

    dp[0][0] = 0;

    for(int i=0; i<N; i++) {
        for(int j=0; j<MAXZ; j++) {
            ll next_seat = arr[i].second + j;
            if(next_seat < MAXZ) {
                dp[i+1][next_seat] = min(dp[i+1][next_seat], dp[i][j] + arr[i].first);
            }
            dp[i+1][j] = min(dp[i+1][j], dp[i][j]);
        }
    }

    ll ans = INF;
    for(int i=0; i<MAXN; i++) {
        for(int j=need_seats; j<MAXZ; j++) {
            ans = min(ans, dp[i][j]);
        }
    }

    cout<<ans<<endl;
}


int main() {
    // speed up
    ios::sync_with_stdio(0);
	cin.tie(0);

    solve();

    return 0;
}