사격 연습

$N \times N$ 크기의 보드 판에는 1개 이상의 표적이 있다. 한 학생이 사격을 연습하고 있으며, 1번부터 $K$번까지 $K$개의 총알을 가지고 있다. 학생은 1번 총알부터 $K$번 총알까지 차례대로 발사하여 총 $K$번 사격한다.

한 번의 사격에서는 1행부터 $N$행 중 한 행을 골라 사격한다. 총알은 가장 왼쪽 열(1열)의 한 위치에서 출발하여 왼쪽에서 오른쪽으로 한 칸씩 수평으로 날아간다. 각 총알은 공격력을 가진다.

초기 입력에서 표적이 있는 위치는 1 이상의 자연수로 표시되고, 표적이 없는 곳은 0으로 표시된다. 표적이 있는 위치의 값은 초기 체력(시작 시점의 현재 체력)을 의미한다. 이후 총알이 표적에 닿으면 현재 체력이 총알의 공격력만큼 줄어든다. 총알은 표적을 관통하지 못하며, 표적에 닿은 총알은 즉시 사라진다.

총알에 맞아 현재 체력이 0 이하가 되면 표적은 사라진다. 이때 학생은 그 표적의 초기 체력만큼 점수를 얻는다. 그다음 사라진 표적의 상, 하, 좌, 우 칸 중 표적이 없는 빈 칸마다 새 표적이 생성된다. 새 표적의 초기 체력은 사라진 표적 초기 체력의 1/4이며, 소수점 아래는 버린다. 그 값이 0이면 새 표적은 생성되지 않는다.

처음에는 모든 표적의 초기 체력과 현재 체력이 같다. 값이 10 이상인 표적은 보너스 표적이다. 보너스 표적은 별도의 초기 체력이 없다. 총알이 보너스 표적에 맞으면 총알의 공격력과 상관없이 총알과 보너스 표적이 함께 사라지고, 보너스 표적에 적힌 점수를 즉시 얻는다. 보너스 표적은 사라진 뒤 새 표적을 생성하지 않는다. 보너스 표적이 아닌 일반 표적의 초기 체력은 1 이상 9 이하의 자연수다.

$N \times N$ 크기의 초기 보드 판 정보가 주어질 때, $K$번의 사격으로 얻을 수 있는 점수의 최댓값을 구하시오. $K$번의 사격은 모두 같은 위치(같은 행)에서 수행할 수 있다. 각 총알의 공격력은 1 이상 100 이하의 자연수다.

예를 들어 $N=5$, $K=3$인 경우를 생각해 보자. 각 총알의 공격력은 차례대로 1, 5, 1이라고 하자. 이때 사격할 수 있는 위치는 총 5개다. 초기 점수는 0점이다.

1. 첫 번째 총알의 공격력은 1이다. 위치 2에서 사격하면 보너스 표적을 맞히고, 점수가 10점이 된다.

2. 두 번째 총알의 공격력은 5이다. 위치 2에서 사격하면 일반 표적을 맞히고, 점수가 14점이 된다.

3. 세 번째 총알의 공격력은 1이다. 위치 1에서 사격하면 일반 표적을 맞히고, 점수가 15점이 된다.

위와 같이 사격했을 때 점수가 15점이 되며, 이 경우가 최댓값이다.

첫째 줄에 보드 판의 크기 $N$이 자연수로 주어진다. $N$은 2 이상 8 이하의 자연수다. 둘째 줄에 사격 횟수 $K$가 자연수로 주어진다. $K$는 1 이상 5 이하의 자연수다. 셋째 줄부터 $N+2$번째 줄까지 $N \times N$ 크기의 보드 정보가 주어진다. 각 위치의 값은 공백으로 구분되며, 0 이상 30 이하의 정수다. $N+3$번째 줄에는 1번부터 $K$번까지 각 총알의 공격력이 공백으로 구분되어 차례대로 주어지며, 각 공격력은 1 이상 100 이하의 자연수다.

$K$번의 사격이 가능할 때, 얻을 수 있는 최대 점수를 첫째 줄에 자연수로 출력한다.