16127번 - 미생물 키우기

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

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

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

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

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

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

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

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

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

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

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

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

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