Sample text

#include <bits/stdc++.h>

#define x first
#define y second
#define all(x) (x).begin(), (x).end()
#define itn int

using namespace std;

inline int nxt(){
    int x;
    scanf("%d", &x);
    return x;
}

int main(){

    int n = nxt();
    vector<pair<pair<int, int>, int> > a(n);
    for (int i = 0; i < n; i++){
        a[i].x.x = nxt();
        a[i].x.y = nxt();
        a[i].y = nxt();
    }
    int ans = -1;
    int s = 0;
    for (int i = 0; i < n; i++)
        s += a[i].y;
    clock_t start = clock();
    for (int it = 0;; it++){
        if (it % 1000 == 0){
            if (clock() - start > 1.7 * CLOCKS_PER_SEC)
                break;
        }
        int q, w;
        do {
            q = rand() % 10000;
            w = rand() % 10000;
            if (rand() % 2)
                w = -w;
        } while (!q && !w);
        auto cmp = [q, w](const pair<pair<int, int>, int>& x, const pair<pair<int, int>, int>& y){
            return q * x.x.x + w * x.x.y < q * y.x.x + w * y.x.y;
        };
        sort(all(a), cmp);
        int cur = 0;
        for (int i = 0; i < n; i++){
            if (ans == -1 || abs(s - cur - cur) < ans){
                ans = abs(s - cur - cur);
            }
            cur += a[i].y;
        }
    }
    printf("%d\n", ans);

    return 0;
}