密码配额（quota）

题目描述

某实验室正在准备一批特殊材料。

共有 (n) 份不同的材料，每份材料都有一个正整数编号 $(a_i) 和使用价值 (v_i)$。

材料需要消耗的资源数量由其编号决定：

资源消耗量等于编号中所有十进制数字的乘积。

例如：

• 编号 23 的材料，资源消耗量为 $(2\times3=6)$；
• 编号 111 的材料，资源消耗量为 $(1\times1\times1=1)$。

每份材料最多只能使用一次。

实验室要求选中材料的资源消耗量之和必须恰好等于 (V)。

在满足要求的前提下，求最大总价值。

如果不存在满足要求的方案，输出 -1。

输入格式

第一行包含两个整数 (n,V)。

接下来 (n) 行，每行包含两个整数 $(a_i,v_i)$。

输出格式

输出最大总价值，无解输出 -1。

输入输出样例 #1

输入

4 9
12 3
23 8
34 12
111 2

输出

13

样例解释

编号为 12、23、111 的三份材料，资源消耗量分别为 2、6、1。

选择这三份材料，可以恰好消耗：

2+6+1=9

获得总价值：

3+8+2=13

数据范围

• $(1\le n\le100)$
• $(1\le V\le2000)$
• $(1\le a_i\le9999)$
• $(1\le v_i\le10000)$

特别保证：每个编号的十进制表示中都不含数字 0。