C. Banknotes

C. Banknotes

In Berland, nn different types of banknotes are used. Banknotes of the ii-th type have denomination 10ai10ai burles (burles are the currency used in Berland); the denomination of banknotes of the first type is exactly 11.

Let's denote f(s)f(s) as the minimum number of banknotes required to represent exactly ss burles. For example, if the denominations of banknotes used in Berland are 11, 1010 and 100100, then f(59)=14f(59)=14: 99 banknotes with denomination of 11 burle and 55 banknotes with denomination of 1010 burles can be used to represent exactly 9⋅1+5⋅10=599⋅1+5⋅10=59 burles, and there's no way to do it with fewer banknotes.

For a given integer kk, find the minimum positive number of burles ss that cannot be represented with kk or fewer banknotes (that is, f(s)>kf(s)>k).

Input

The first line contains a single integer tt (1≤t≤1041≤t≤104) — number of test cases.

The first line of each test case contains two integers nn and kk (1≤n≤10;1≤k≤1091≤n≤10;1≤k≤109).

The next line contains nn integers a1,a2,…,ana1,a2,…,an (0=a1

Output

For each test case, print one integer — the minimum positive number of burles ss that cannot be represented with kk or fewer banknotes.

题解

       （ 本题是codeforces上的一道题，原题地址请自己去查。）

        题目大概的意思是给你n种不同的面值的钞票，然后让你从这n种币值任意的选择k张钞票，组成一个最小的金额且不能被更少的张数的钞票组合所表示。比如有1，10，100这三种币值，有10张纸币，我们要选9张1元和1张10元，共19元。10张1元是不行的，虽然金额最小但不能满足无法被更少的钞票取代，1张10元就可以表示10元了。值得注意的是题目是大于关系而不是大于等于，所以我们的所进行选择时要选择k+1张钞票.

        根据题意，先把面额最小的钞票选满，然后依次类推，剩下的钞票只能全部选择最后的面额。

代码如下

#include
using namespace std;
 
int main(){
    int t;
    cin>>t;
    while(t--){
        int n,note[10];
        long long k,ans=0;
        cin>>n>>k;
        for(int i=0;i>temp;
            temp=pow(10,temp);
            note[i]=temp;
        }
        for(int i=0;k!=0;i++){
            if(i==n-1) {ans+=note[i]*(k+1);k-=k;break;}
            if((note[i+1]/note[i]-1)<=k) {
                    k-=note[i+1]/note[i]-1;ans+=(note[i+1]/note[i]-1)*note[i];
                    if(k==0) ans+=note[i+1];
            }
            else {ans+=note[i]*(k+1);k-=k;}
        }
        cout<