A - Adventures in Moving Part IV (1-12)

#include <bits/stdc++.h>
using namespace std;

const int oo = 1e9 + 7;;

int t, Distance, n;
int dist[105], cost[105];
char s[105];
int dp[105][205];

void Read() {
    scanf("%d", &Distance);
    while(getchar() != '\n');

    n = 1;
    while(gets(s) && s[0]) {
        sscanf(s, "%d %d", &dist[n], &cost[n]);
        n++;
    }
}

void solve() {
    dist[n] = Distance, cost[n] = oo;
    for(int i = 0; i <= n; i++)
        for(int j = 0; j <= 200; j++)
            dp[i][j] = oo;
    dp[0][100] = 0;

    for(int i = 1; i <= n; i++) {
        int dis = dist[i] - dist[i-1];

        for(int j = dis; j <= 200; j++)
            dp[i][j-dis] = min(dp[i][j-dis], dp[i-1][j]);

        for(int j = 1; j <= 200; j++)
            dp[i][j] = min(dp[i][j], dp[i][j-1] + cost[i]);
    }

    int ans = oo;
    for(int i = 100; i <= 200; i++)
        ans = min(ans, dp[n][i]);

    if(ans == oo) cout << "Impossible" << '\n' << '\n';
    else cout << ans << '\n' << '\n';
}

int main() {
    //freopen("A-Adventures in Moving (Part IV).inp", "r", stdin);
    //freopen("A-Adventures in Moving (Part IV).out", "w", stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    scanf("%d", &t);
    while(getchar() != '\n');
    gets(s);
    while(t--) {
        Read();
        solve();
    }

    return 0;
}
/*
    init = 100;

    dp[0][init - dist[0]] = dp[0][0];

    garToNext = dist[start + 1] - dist[start];
    gasInTank = max(gasLeft, gasToNext);

    dp[start][gasLeft] = min(gasInTank, f[start + 1][gasInTank - gasToNext] + (gasInTank - gasLeft) * cost[start];
*/