ABC 317

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll N;
    cin >> N;
    vll X(N), Y(N), Z(N);
    rep(i, N) cin >> X[i] >> Y[i] >> Z[i];

    ll totz = accumulate(all(Z), 0ll);
    // dp[m]: m 議席獲得するのに必要なコストの最小値
    vll dp((ll)totz + 1, INF);
    dp[0] = 0;

    rep(i, N) {
        for (ll z = totz; z - Z[i] >= 0; z--) {
            // 高橋派にするのに必要なコスト
            ll cost = X[i] > Y[i] ? 0 : Y[i] - (X[i] + Y[i]) / 2;
            chmin(dp[z], dp[z - Z[i]] + cost);
        }
    }

    ll ans = INF;
    rep2(z, ceil(totz, 2), totz + 1) {
        chmin(ans, dp[z]);
    }
    cout << ans << endl;
}

void solve() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

    ll H, W;
    cin >> H >> W;
    vector<string> eye_grid(H);
    rep(i, H) cin >> eye_grid[i];

    int si = -1, sj = -1, fi = -1, fj = -1;

    string sight = ">v<^";
    vint di = {0, 1, 0, -1};
    vint dj = {1, 0, -1, 0};

    vector<string> grid(H, string(W, '.'));

    rep(i, H) rep(j, W) {
        char c = eye_grid[i][j];
        if (c == 'S') si = i, sj = j;
        if (c == 'G') fi = i, fj = j;
        if (c == '.') continue;
        if (c == '#') {
            grid[i][j] = '#';
            continue;
        }

        rep(d, 4) {
            if (c != sight[d]) continue;
            grid[i][j] = '#';
            ll x = i, y = j;
            while (true) {
                ll ni = x + di[d], nj = y + dj[d];
                if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj)
                    break;
                if (eye_grid[ni][nj] != '.') break;
                grid[ni][nj] = '#';

                x = ni, y = nj;
            }
        }
    }

    using P = pair<ll, ll>;
    queue<P> que;
    que.push({si, sj});

    vvll dist(H, vll(W, INF));
    dist[si][sj] = 0;

    while (que.size()) {
        auto [i, j] = que.front();
        que.pop();

        rep(d, 4) {
            ll ni = i + di[d], nj = j + dj[d];
            if (clamp(ni, 0ll, H - 1) != ni || clamp(nj, 0ll, W - 1) != nj) continue;
            if (grid[ni][nj] == '#') continue;

            if (dist[ni][nj] > dist[i][j] + 1) {
                dist[ni][nj] = dist[i][j] + 1;
                que.push({ni, nj});
            }
        }
    }

    ll ans = dist[fi][fj];
    if (ans == INF) ans = -1;
    cout << ans << endl;
}