Help-or-else O(n^3) - Live Archive 5688 AC

#include <stdio.h>
#include <algorithm>
#include <string.h>
using namespace std;

const int inf =0x3f3f3f3f;

struct assist {
    int d,e;
};

int n,k;
int dp[210][210];
assist p[210];
int np;
int _42=1;

bool cmp(assist a, assist b) {
    if (a.d==b.d)
        return a.e<b.e;
    return a.d<b.d;
}

int main() {
    while (1) {
        scanf("%d %d", &n,&k);
        if (!n && !k) break;

        for (int i=0; i<n; i++)
            scanf("%d %d", &p[i].e, &p[i].d);
        sort(p,p+n,cmp);

        for (np=n; np>=0; np--) {
            memset(dp,0x3f,sizeof(dp));

            dp[0][np]=p[0].e;
            dp[0][np-1]=np*p[0].d;

            for (int i=1; i<n; i++)
                for (int j=np; j>=0; j--)
                    dp[i][j]=min(dp[i-1][j]+p[i].e,
                        dp[i-1][j+1]+p[i].d*(j+1));

            if (dp[n-1][0]<=k)
                break;
        }

        if (np!=-1) printf("%d: %d\n" ,_42++, np);
        else printf("%d: Mission Impossible\n", _42++);
    }

    return 0;
}