UVA 12124 Assemble (UVALive 3971, HDU 2333, POJ 3497, ZOJ 3090, Regionals 2007 >> Europe - Northwestern)

///     Raihan Ruhin
///     CSE, Jahangirnagar University.
///     Dhaka-Bangladesh.
///     id: raihanruhin (topcoder / codeforces / codechef / uva / uvalive), 3235 (lightoj)
///     mail: raihanruhin@ (yahoo / gmail / facebook)
///     blog: ruhinraihan.blogspot.com

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

#define SET(a) memset(a,-1,sizeof(a))
#define CLR(a) memset(a,0,sizeof(a))
#define PI acos(-1.0)

#define MOD 1000000007
#define MX 100010

struct product{
    int price, quality;
    bool operator < (const product &p) const
    {
        if(price==p.price) return quality>p.quality;
        return price<p.price;
    }
};

product Pdt;

int main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);
    int tc, kk=1, n, m, x, y, a, b, c, p, q;
    long long budget;
    string s;
    cin>>tc;
    while(tc--)
    {
        cin>>n>>budget;
        map<string, int>mp;
        vector<product>type[1005];
        set<int>totQ; //total quality available
        int cnt=1;
        for(int i=0;i<n;i++)
        {
            cin>>s;
            if(mp[s]==0)
            {
                mp[s]=cnt;
                cnt++;
            }
            cin>>s;
            cin>>Pdt.price>>Pdt.quality;
            type[cnt-1].push_back(Pdt);
        }
        for(int i=1;i<cnt;i++)
        {
            sort(type[i].begin(), type[i].end());
            for(int j=1;j<type[i].size();j++)
            {
                while(type[i][j].quality <= type[i][j-1].quality && j<type[i].size())
                    type[i].erase(type[i].begin()+j);
            }
        }


        for(int i=1;i<cnt;i++)
            for(int j=0;j<type[i].size();j++)
                totQ.insert(type[i][j].quality);
        int idx[cnt+2];
        CLR(idx);
        int ans=-1;
        bool brk=false;
        for(auto i:totQ)
        {
            long long tot=0;
            for(int j=1;j<cnt;j++)
            {
                while(type[j][idx[j]].quality<i && idx[j]<type[j].size()) idx[j]++;
                if(idx[j]==type[j].size())
                {
                    brk=true;
                    break;
                }
                tot+=(long long) type[j][idx[j]].price;
            }
            if(brk) break;
            if(tot>budget) break;
            ans=i;
        }
        cout<< ans <<"\n";
        mp.clear();
        for(int i=1;i<cnt;i++) type[i].clear();
    }
return 0;
}