MULTII - Yet Another Multiple Problem

Given a positive integer N (1 <= N <= 10000) and some digits, find the smallest positive multiple of N whose decimal notation does not contain any of the given digits.

Input

Each test case contains two lines. The first line contains two integers N and m separated by a single space. The second line contains m digits separated by spaces. Input terminates by EOF.

Output

For each test case output its case number (starting from 1) and the answer in a single line, or "-1" (without quotes) if the answer doesn't exist.

Example

Input:
2345 3
7 8 9
100 1
0

Output:
Case 1: 2345
Case 2: -1

Added by:Fudan University Problem Setters
Date:2012-11-21
Time limit:4s
Source limit:50000B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:All except: ASM64
Resource:ACM/ICPC Regional Contest, Chengdu 2012

hide comments
2012-12-11 22:24:17 Darko Aleksic
Got RTE when trying to print the number recursively. This is a general request - can the Java stack be increased?

I knew I've seen this problem somewhere before:
http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=21&page=show_problem&problem=1934

Last edit: 2012-12-11 22:57:04
2012-12-01 08:19:35 devu
Could You Just tell me the maximum length of the answer which would be coming..

Getting Runtime Error on 2012-12-01 , And on 10-08-2013 ..it's Accepted...The question asked by me is foolish ..I admit admin ...No reason for so less submission..straight forward problem :D

Last edit: 2013-08-09 18:32:40
2012-11-21 17:48:31 (Tjandra Satria Gunawan)(曾毅昆)
Ok, I give up, this problem is too hard for me for now...
In case like this:
2791 9
0 2 3 4 5 6 7 8 9
answer is not -1 but answer is 1111111111111111111111111111111
so it's very large integer :-O
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.