Mafia

Eunjin has realized that she is the last remaining mafia player in a mafia game. Every other participant is a citizen, and participants are numbered from 0 to N-1.

The game alternates between night and day according to the number of survivors. If the number of survivors is even, it is night; if it is odd, it is day. If the mafia player is gone, the citizens win. If no citizens remain, the mafia wins. The game ends immediately when either condition is met.

Each participant has a guilt score. During the day, the living participant with the highest guilt score is eliminated. If several participants tie, the one with the smallest number is eliminated. Guilt scores do not change during the day.

At night, Eunjin chooses one participant to eliminate. If participant i is eliminated at night, every other participant j has their guilt score changed by R[i][j].

Assuming Eunjin always chooses optimally to keep the game going as long as possible, find the maximum number of nights that can pass.

The first line contains the number of participants N.

The second line contains N guilt scores, one for each participant.

The next N lines contain the reaction array R. Each line has N integers, and the j-th number on the i-th line is R[i][j].

The last line contains the participant number of Eunjin.

N is a positive integer not greater than 16. Each guilt score is a positive integer from 300 to 800, inclusive. Every value in R is an integer whose absolute value is from 1 to 26, inclusive.

Print the maximum number of nights that can pass when Eunjin plays optimally.