Light OJ 1079 / DP-Probability (like coin change)

/***
 created: 2022-08-30-01.23.10
***/

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;
template<typename U> using ordered_set=tree<U, null_type,less<U>,rb_tree_tag,tree_order_statistics_node_update>;
#define ll long long
#define test int tt; cin>>tt; for(int cs=1;cs<=tt;cs++)
#define get_lost_idiot return 0
#define nl '\n'

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    test
    {
        ll n,m=0,i,j,k=0,l=0;

        double exp,dp[10005];;

        cin>>exp>>n;

        for(i=0;i<10002;i++) dp[i]=0.00;

        ll mn[n+4];

        double p[n+4];

        for(i=0;i<n;i++)
        {
            cin>>mn[i]>>p[i];
            l+=mn[i];
            p[i]=1.00-p[i];
        }

        dp[0]=1.00;

        for(i=0;i<n;i++)
        {
            for(j=l;j>=mn[i];j--)
            {
                if(dp[j-mn[i]]!=0)
                {
                    dp[j]=max(dp[j],dp[j-mn[i]]*p[i]*1.00);
                }
                if(1.00-dp[j]<exp)
                {
                    k=max(k,j);
                }
            }
        }

        cout<<"Case "<<cs<<": "<<k<<nl;
    }

    get_lost_idiot;
}