[[problem:SUSHI]]
이문제를 다이나믹 넵섹 문제 풀듯이 접근하였는데 메모리 낭비를 하지 않기 위해 (돈,선호도)이런식으로 순서쌍을 가져서 해결하려했는데 계속 시간초가가 나오네요 ㅜㅜ 푸신분들있으면 어떻케풀었는지 알려주세요

이건제소스입니다

#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <deque>
using namespace std;
#define  oo 21474837
typedef pair<long,long> P;
struct input{
    long long int money,profit;
};
input data[21];
int n,m;
int ans;
deque<P> dp[2];
priority_queue<P,vector<P>,greater<P> >que;
int cmp(const input &a,const input &b)
{
    if(a.money==b.money)return a.profit>b.profit;
    return a.money<b.money;
}
void dynamic()
{
    int i;
    long j;
    int past=-1;
    ans=0;
    P a,b,c;
    a.first=0;
    a.second=0;
    dp[1].push_back(a);
    for(i=0;i<n;i++)
    {
        if(past>data[i].profit)continue;
        past=data[i].profit;
        a.first=data[i].money;
        a.second=data[i].profit;
        dp[i%2].clear();
        while(!dp[(i+1)%2].empty())
        {
            b=dp[(i+1)%2].front();
            dp[(i+1)%2].pop_front();
            que.push(b);
            for(j=1;;j++)
            {
                if(b.first+a.first*j>m)break;
                else
                {
                    c.first=b.first+a.first*j;
                    c.second=b.second+a.second*j;
                    que.push(c);
                }               
            }
            while(!que.empty())
            {
                c=que.top();
                if(ans<c.second)ans=c.second;
                dp[i%2].push_back(c);
                if(dp[i%2].size()>1)
                {
                    if(dp[i%2][dp[i%2].size()-2]>dp[i%2][dp[i%2].size()-1])dp[i%2].pop_back();
                }
                que.pop();
                
            }
        }
    }
}
int main()
{
    int C,i;
    cin>>C;
    while(C--)
    {
        cin>>n>>m;
        m/=100;
        for(i=0;i<n;i++)
        {
            cin>>data[i].money>>data[i].profit;
            data[i].money/=100;
        }   
        sort(data,data+n,cmp);
        dynamic();
        cout<<ans<<endl;
    
    }
    return 0;
}