미생물 키우기

범수는 오늘도 방에서 미생물을 키운다. 미생물은 총 $N$가지가 있으며 1번 미생물부터 $N$번 미생물까지 번호가 매겨져 있다. 범수는 여러 종류의 미생물을 키우려 한다. 구체적으로, $1 \le i \le N$인 모든 정수 $i$에 대해 $i$번 미생물을 $x_i$개 만들려 한다.

미생물을 만드는 방법은 두 가지다.

• $1 \le i \le N$인 임의의 정수 $i$에 대해, $i$번 미생물 하나를 사서 방에 넣는다. $i$번 미생물을 사는 데는 $y_i$만큼 비용이 든다.

• $1 \le i, j \le N$인 임의의 두 정수 $i$와 $j$에 대해, $i$번 미생물에게 특수한 약을 먹여 $j$번 미생물을 만들도록 시킨다. 이 연산은 $i$번 미생물이 이미 방에 있을 때만 할 수 있으며, $i$번 미생물이 $j$번 미생물 하나를 만드는 데 $z_{i,j}$만큼 비용이 든다. $i$와 $j$는 같을 수 있다.

범수는 처음에 아무런 미생물도 가지고 있지 않다. 범수가 두 방법을 적당히 사용하여 목적을 달성하는 데 드는 최소 비용을 출력한다.

첫째 줄에 미생물의 수 $N$($1 \le N \le 300$)이 주어진다.

둘째 줄에 $N$개의 수가 공백을 사이에 두고 주어진다. 이 중 $i$번째 수는 범수가 만들고자 하는 $i$번 미생물의 수 $x_i$($1 \le x_i \le 10^6$)를 의미한다.

셋째 줄에 $N$개의 수가 공백을 사이에 두고 주어진다. 이 중 $i$번째 수는 $i$번 미생물을 사 오는 데 드는 비용 $y_i$($1 \le y_i \le 10^9$)를 의미한다.

넷째 줄부터 $N$개의 줄에 각각 $N$개의 수가 주어진다. 이 중 $i$번째 줄의 $j$번째 수는 $i$번째 미생물이 $j$번째 미생물을 만들 때 드는 비용 $z_{i,j}$($1 \le z_{i,j} \le 10^9$)를 의미한다.

첫째 줄에 범수가 목적을 이루기 위한 최소 비용을 출력한다.

위 예시의 답은 아래와 같다.

1. 1번 미생물을 사 온다. 이때 드는 비용은 $y_1 = 2$이다.
2. 1번 미생물에게 약을 먹여 2번 미생물을 하나 만들게 한다. 이때 드는 비용은 $z_{1,2} = 1$이다.
3. 2번 미생물에게 약을 먹여 1번 미생물을 하나 만들게 한다. 이때 드는 비용은 $z_{2,1} = 1$이다.
4. 2번 미생물에게 약을 먹여 2번 미생물을 하나 만들게 한다. 이때 드는 비용은 $z_{2,2} = 1$이다.

이때 비용의 합은 5이며 이 방법이 최적이다.