Primest Prime Pancakes

In order to make some extra money, Stefan decided to open a brand new pancake house for the upcoming summer season, because after all, who wouldn’t buy some wonderful pancakes during the summer holiday?

The house is going to sell $n$ different types of pancakes, each labeled with a certain number, based on its type. Now, in order to find the price of a pancake, Stefan decided to use his imagination and come up with a really interesting algorithm for deciding the price of a pancake.

Namely, because prime numbers are his favorite, the price is going to depend on how prime a pancake is.

Therefore:

• The base price of a pancake is $x$ euro, where $x$ is given in the input.
• If the label of the pancake is prime, the price increases by label $+\ p$ euro, where label is the value of the label and $p$ is given in the input.
• For each prime digit of the label ($2, 3, 5, 7$), the price will increase by $d_i$ euro, where $d_i$ values are given in the input.
• If the sum of the digits of the label is prime, the price increases by $sc$ euro, where $sc$ is the sum of digits of the label.
• If the product of the digits of the label is prime, the price will increase by $pd$ euro, where $pd$ is the product of the digits of the label.

Obviously, this may not lead to enough profit and now it’s time for you to step in and help Stefan get the highest profit by changing at most one digit from each label in order to maximize the sum of prices of all the pancake labels.

However, you can’t make the most significant digit become $0$ and thus getting a number with one less digit, even though it might be the most lucrative option.

Input

The first line of the input will have an integer $n$ ($1 \le n \le 10^5$), representing the pancakes which are initially available in Stefan’s pancake house.

The second line of the input will have $n$ integers, representing the initial labels of the pancakes ($1 \le l_i \le 999 \ 999$).

The third line of the input will have two values, $x$ and $p$ ($1 \le x, p \le 10^6$), explained in the statement.

The fourth line of the input will have four values, $d_2$, $d_3$, $d_5$, $d_7$ ($1 \le d_i \le 10^6$).

For tests worth $30$ points, ($1 \le n \le 1 \ 000$).

Output

The output will contain a single line, representing the maximum possible profit Stefan can get by changing conveniently some of the pancake labels according to the rule from the statement.

Example

stdin

4
12 89 941 101
5 7
8 5 3 9

stdout

1907

Explanation

We should change the first value from 12 to 17 and that would lead us to a value of 45.

It is optimal to keep the second value to be 89 for a value of 118.

We should change the third value from 941 to 991 and that would lead us to a value of 1022.

We should change the fourth value from 101 to 701 and that would lead us to a value of 722.

The sum of values will become 1907.