Ignore my post above, I misunderstood the problem statement.

But still, even if you understand, i still don't. In case of
4 1
1000 5
1000 5
1000 5
1000 5
2 10
or even, if we're not allowed to use the same subscription twice,
4 2
1000 5
1000 5
1000 5
1000 5
2 10
2 10
, why can't we have 3600? That is, if i understood you correctly...

correct answer for 0 is 10.
maybe this fact help you.

Try n=1234.Output is -1.

How about N = 13 ? ;)

my solution in c++ 0.031 s.
#include<iostream>
#include<cmath>
#include<string>
#include<algorithm>
using namespace std;

inline bool isprime(long a)
{
    if(a==1)return false;
    if(a==2)return true;
    if(a%2==0)return false;
    for(int i=3;i<sqrt(a);i+=2)
    {

        if(a%i==0)return false;
    }
    return true;



}


int main()
{
    string a;
    long n;
    int d=1;
    cin>>n;
    if(n==0)cout<<"10"<<endl;
    else if(n==1)cout<<"1"<<endl;
    else{
    if(isprime(n) && n>10)d=0;
    else
    {
        int gamyop=9;
        while(n!=1)
        {

            if(n%gamyop==0)
            {
                a+=(gamyop+'0');
                n/=gamyop;
                if(isprime(n) && n>10){d=0;break;}

            }
            else
            {
                gamyop--;
            }


        }



    }
    sort(a.begin(),a.end());
    if(d==1)cout<<a<<endl;
    else cout<<"-1"<<endl;
    }

    return 0;
}

I used recursive algorithm. (C++)
result and local variables in function must be __int64(long long)
In other cases you'll get an overflow
Usage of string not are obligatory

Test#8 is:

N=1 000 000 000
Q->555555555888

for examle with local or result variables of type unsigned you'll get
Q->1504774704

Sorry for my English :)