시간 제한 메모리 제한 제출 정답 맞은 사람 정답 비율
2 초 (추가 시간 없음) 512 MB 88 25 13 25.000%

문제

범수는 오늘도 방에서 미생물을 키운다. 미생물은 총 N가지가 있으며 이들은 1번 미생물부터 N번 미생물까지 번호가 매겨져 있다. 범수는 다양한 미생물들을 키우려 한다. 구체적으로, 1 ≤ iN를 만족하는 모든 정수 i에 대해 i번 미생물을 xi개 만들려 한다.

미생물을 만드는 데는 다음 두 가지 방법이 있다.

  • 1 ≤ iN을 만족하는 임의의 정수 i에 대해, i번 미생물 하나를 사서 방에 넣는다. i번 미생물을 사는 데는 yi만큼 비용이 든다.

  • 1 ≤ i, jN을 만족하는 임의의 두 정수 ij에 대해, i번 미생물에게 특수한 약을 먹여 j번 미생물을 만들도록 시킨다. 이 연산은 i번 미생물이 이미 방에 있을 때만 할 수 있으며, i번 미생물이 j번 미생물 하나를 만드는 데 zi,j만큼 비용이 든다. ij는 같을 수 있다.

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

입력

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

둘째 줄에 N개의 수가 공백을 사이에 두고 주어진다. 이 중 i번째 수는 범수가 만들고자 하는 i번 미생물의 수 xi(1 ≤ xi ≤ 106)를 의미한다.

셋째 줄에 N개의 수가 공백을 사이에 두고 주어진다. 이 중 i번째 수는 i번 미생물을 사 오는 데 드는 비용 yi(1 ≤ yi ≤ 109)를 의미한다.

넷째 줄부터 N개의 줄에 각각 N개의 수가 주어진다. 이 중 i번째 줄의 j번째 수는 i번째 미생물이 j번째 미생물을 만들 때 드는 비용 zi,j(1 ≤ zi,j ≤ 109)를 의미한다.

출력

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

예제 입력 1

2
2 2
2 8
4 1
1 1

예제 출력 1

5

노트

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

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

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