【NC2022】比k大的数

题目描述

一个不含0的n位数，其中值等于i的数码有ci个(1≤i≤9)。在这个n位数的所有可能的值中，比k大的值最小是多少？

输入

第1行，2个正整数n,k。

第2行，9个非负整数c1,c2,…,c9,分别表示1~9的个数。

对于25%的数据，n≤9；k≤109109。

对于50%的数据，n≤200；k≤1020010200

对于100%的数据，1≤n≤500000；1≤k<1050000110500001

ci>=0,c1+c2+c3+c4+c5+c6+c7+c8+c9=n。

输出

输出所有可能的值中，比k大的值的最小值。

如果没有比k大的值，输出-1。

样例

输入复制

3 213
1 1 1 0 0 0 0 0 0

输出复制

231

输入复制

4 4000
1 0 2 1 0 0 0 0 0

输出复制

4133

输入复制

3 9999
1 1 1 0 0 0 0 0 0

输出复制

-1

说明

输入样例4:
21 791823456795285473500
1 2 2 3 2 3 2 3 3
输出样例4:
791823456795286344689

【样例1说明】
有1个1、1个2、1个3，可能的值有123,132,213,231,312,321，共6个。其中，比k=213大的最小值是231。

【样例2说明】
有1个1、2个3、1个4，可能的值有
1334,1343,1433,3134,3143,3314,3341,3413,3431,4133,4313,4331共12个。其中，比k=4000大的最小数是4133。

【样例3说明】
有1个1、1个2、1个3，可以得到的最大值321都比k=9999小，所以无法得到比k大的值。

【样例4说明】
输入输出可能超过64位整数类型范围。