As you all know this is the time for college admissions. So all the colleges and students are applying for admissions in different colleges.

In the city of Mariejois there are N colleges and N students. Each student is has rank from 1 to N. Now each student decides to enter a college within a city. But each student has his personal preference to choose the college according to his wish. Naturally the colleges have competition among themselves and have varying tuition fees of themselves. Now as being insecure about their admissions they lower the prices by some amount if a student gets admission in some other college.

Formally:
If a student gets admission in a college A and college B is dependent on college A, then college B will reduce its fee by X amount. So if any other student gets admission in college B then he will have to pay $fee= fee(B) - X$.

Now each student must get admission in exactly one college. Student starting from the 1st will select his/her college first and then sequentially 2nd, 3rd and so on the students will select their colleges.
So you have to help the students to enter the colleges according to their preferences and in a certain serial arrangement such that the total fees paid by all the students together is minimum.

Note
It is guaranteed that there is at least one way in which all the students can be assigned to a particular college according to his/her preferences.
A student ranked below another student cannot select his college first. (Rank matters :p)

Input

First line contains an integer N denoting the number of colleges and students.
Next N lines are described as:
An array of N elements of 0s and 1s denoting the preference of the ith student.
0 shows he is not interested to get admission in the jth college and 1 shows he is.
Next line contains N integers $fee[i]$ which is the initial fee taken by the ith college.
Next N lines are described as:
An integer $dep$ which is the number of colleges that are dependent on the ith college and will lower their fee if a student gets admission in the ith college. Next $2 X dep$ numbers in the ith row are pairwise the index $ind$ of a dependent college and an integer $red$ which is the reduction in the fee that the dependent college will make.

Output

Output the minimum total fee paid by all the students together in the first line.
Second line should contain N integers where $ith$ integer shows the college of the $ith$ student.
PS: If there multiple ways to achieve minimum total amount print any one of them.

Constraints:

$1\leq N \leq 16$
$1\leq fee[i] \leq 10^{6}$
$0\leq dep < N$
$1\leq Ind \leq N$
$1\leq red \leq 10^{6}$