Complan Carnival SPOJ

Pitanje ili opis problema

Zadatak sa SPOJa

Link ka zadatku ili odgovarajućoj stranici

Postovani,
Naleteo sam skoro na ovaj problem i imam TLE zbog velike kompleksnosti. Koliko shatam imam sort sto je O(nlogn) valjda + knapsack problem (samo ne igram loto nego stavljam resenja u vektor) sto je O(n(n+1)/2) (svaki sa svakim u najgorem slucaju)
Ovo je kod:

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;

class voznja
{
	public:
		int cena=0, plus=0, visina=0;
		voznja();
		voznja(int, int, int);
		bool operator <(voznja);
};

class triplet
{
	public:
		int x1, x2, x3;
		triplet();
		triplet(int, int, int);
};

triplet::triplet(int j, int k, int l)
{
	x1=j;
	x2=k;
	x3=l;
}

voznja::voznja(int x, int y, int z)
{
	cena=y;
	visina=x;
	plus=z;
}
bool voznja::operator<(voznja neka)
{
	if(visina<neka.visina)return true;
	else if(visina>neka.visina)return false;
	else
	{
		if(cena<neka.cena)return true;
		else return false;
	}
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	vector<voznja> c;
	vector<triplet> stanja;
	int n, m, h, w1, w2, w3, cnt=0, maxi=-1;
	cin>>n>>m>>h;
	for(int i=0; i<n; i++)
	{
		cin>>w1>>w2>>w3;
		if(w2==0)cnt++, h+=w3;
		else if(w2<m)
		c.push_back(voznja(w1, w2, w3));
	}
	sort(c.begin(), c.end());
	stanja.push_back(triplet(h, m, cnt));
	for(voznja v : c)
	{
		for(int i=stanja.size()-1; i>=0; i--)
		{
			if(v.visina<=stanja[i].x1 && v.cena<=stanja[i].x2)
			{
				stanja.push_back(triplet(stanja[i].x1+v.plus, 0-v.cena+stanja[i].x2, stanja[i].x3+1)); if(maxi<stanja[i].x3+1)maxi=stanja[i].x3+1;
			}
		}
	}
	cout<<maxi;
	
	return 0;
}

Ako postoji neko dinamicnije resenje bio bih zahvalan na sugestiji
PS: pod loto mislim da se knapsack ne radi preko niza sa nulama pa tu satvim 1 ako postoji vrednost, tako sam ucio knapsack pa cisto da napomenem

Da dodam samo sam sam video jednu gresku, kod if(w2==0) bi trebao da dodam i za visinu proveru jer ako nije dovoljno visok nebitno je sto je besplatna voznja, ali mislim da to nije krucijalno