402387: GYM100741 I Card Jousting

Memory Limit:32 MB Time Limit:0 S
Judge Style:Text Compare Creator:
Submit:0 Solved:0

Description

I. Card Joustingtime limit per test0.25 secondsmemory limit per test32 megabytesinputstandard inputoutputstandard output

Iahub and Iahubina are playing a card game. Each of them has N cards on which are written numbers. Even if Iahub loves Iahubina very much, he wants to win this game. In order to do that he needs to win all the rounds. A round consists in the choice of the card by Iahubina which will be removed afterwords. Iahub also has to choose a card from his deck, which will be removed afterwords as well. Let B be the card chosen by Iahubina and A the card chosen by Iahub. Iahub can win only if A|B ≥ K. In addition, Iahub has the possibility to interchange the bits from any two cards, but with a cost. Iahub can interchange the bit i from any card from his deck with the bit j, the cost being cost[i][j]. Find the minimum cost which could lead Iahub to win.

Input

The first line of the input contains an integer N (1 ≤ N ≤ 200). The second line contains a vector A[] with N elements, representing the numbers on Iahubina’s cards. The third line contains a vector B[] with N elements, representing the numbers on Iahub’s cards (1 ≤ A[i], B[i] ≤ 256) On the next line is the integer K (1 ≤ K ≤ 127), followed by 8 lines with 8 values per line, corresponding to the matrix cost[][] (1 ≤ cost[i][j] ≤ 1000, cost[i][j] = cost[j][i]).

Output

Output the minimum cost which would lead Iahub to win.

ExamplesInput
5
127 115 18 81 12
9 73 60 70 19
127
9 7 10 7 5 1 6 1
7 1 9 1 10 2 10 7
10 9 10 9 10 5 10 9
7 1 9 1 5 10 6 7
5 10 10 5 2 3 4 10
1 2 5 10 3 8 5 5
6 10 10 6 4 5 7 1
1 7 9 7 10 5 1 10
Output
10

加入题单

上一题 下一题 算法标签: