Digits Forest

All submissions for this problem are available.
Given a simple undirected graph containing N vertices numbered 1 to N, each vertex containing a digit from {1,2,..7}. Starting at the vertex 1 with an empty string S, we travel through some vertices (with no limitations) to the vertex N. For every vertex on the way, we add the respective digit to the right of the string S. At last we get S as a decimal integer. You are requested to find such a way satisfying S is divisible by all of its digits, and the sum of digits of S must be as small as possible.
Input
There are several test cases (fifteen at most), each formed as follows:
 The first line contains a positive integer N (N ≤ 100).
 The second line contains N digits (separated by spaces), the ith digit is the value of the ith vertex.
 N last lines, each contains N values of {0, 1} (separated by spaces), the jth value of the ith line is equal to 1 if there is an edge connecting two vertices (i, j), otherwise 0.
The input is ended with N = 0.
Output
For each test case, output on a line the minimum sum of digits found, or 1 if there's no solution.
Example
Input: 4 1 2 1 4 0 1 1 1 1 0 0 1 1 0 0 1 1 1 1 0 0 Output: 7
Author:  AnhDQ 
Tester:  subra 
Editorial  http://discuss.codechef.com/problems/DIGFORST 
Tags  anhdq hard may12 
Date Added:  22082011 
Time Limit:  3 sec 
Source Limit:  50000 Bytes 
Languages:  ADA, ASM, BASH, BF, C, C99 strict, CAML, CLOJ, CLPS, CPP 4.3.2, CPP 4.9.2, CS2, D, ERL, FORT, FS, GO, HASK, ICK, ICON, JAVA, JS, LISP clisp, LISP sbcl, LUA, NEM, NICE, PAS fpc, PAS gpc, PERL, PERL6, PHP, PIKE, PRLG, PYTH, PYTH 3.4, RUBY, SCALA, SCM guile, SCM qobi, ST, TCL, TEXT, WSPC 
Comments
 Please login at the top to post a comment.
SUCCESSFUL SUBMISSIONS
Fetching successful submissions