infobean how to solve this question?

7 Star Cities in A State (100 Marks)
In a state of India every city is given 1 to 7 stars according to facilities in
that city.
So lets consider N cities (C1 to Cn) of that state and every city is given a number between 1
to 7 corresponding to level of the cities. Some cities are connected to each other also.

A person plays a
very interesting game. He starts from city C1 and after visiting some cities out of C1 to Cn he finally
ends his journey in city Cn ( he may visit a city multiple times and also he can leave some city also).
During the course of journey the person construct a number ( call this number S) by appending the
rating number of the city in the right of already formed number. Initial he start with empty and append
rating of C1 as he starts with city C1.

The interesting part of the game is that he wants to visit the cities
in a way that the number S formed should be divisible by all its digit and the sum of all the digits of
S should be as less as can be possible.
Input Specification:

  1. A array R of size N corresponding to the rating of N cities
  2. A 2-D array E of size N*N which shows the connectivity of cities. If in this array entry E[i][j] is
    one then it means city Ci is connected to city Cj in graph.

For example: for above example the input would be
Array R of rating would be → {1, 2, 1, 4}
2- D array E of connectivity would be → {0#1#1#1,1#0#0#1,1#0#0#1,1#1#1#0}

Output:
Sum of digits of the number S formed by appending the rating of cities traversed by the person such
that S is divisible by all the digits it contains and the sum is the minimum possible sum.
Note: Output should
be -1 of no solution exits.

Ci- j → here Ci is the city and j is the city rating (1<= j <= 7)
Answer would be C1 → C2 → C4
Number S would be 124
124 is divisible by 1, 2 and 4 as well. And for the above example it is the minimum possible sum