문제
매년, 농부 철수는 품평회에 참가하는 것을 좋아한다.
이번 품평회에는 N개의 노점(1 ≤ N ≤ 400)들이 있고,
각각의 노점은 이 날 특정한 시간 P(i)에(0 ≤ P(i) ≤ 1,000,000,000) 엄청난 '상'을 주려고 계획하고 있다.
농부 철수는 이 소식을 듣고 그의 소들과 이 '상'을 나누기 위해 최대한 많은 상들을 모으려고 한다.
그래서 그는 상들이 주어지는 정확한 시간에 최대한 많은 노점들을 방문해서 상을 모으려고 한다.
농부 철수는 조사를 한 뒤 간 T(i, j) (언제나 1 이상 1,000,000 이하의 범위)를 정했는데,
이는 그가 노점 i에서 노점 j까지 가는데 걸리는 시간을 말한다.
품평회의 특징 중 하나는 노점 i에서 j로 갈 때 그가 중간에 다른 노점을 방문하는 것이 더 빠를 수도 있다는 점이다.
지도를 잘 보지 못하는 철수는 절대로 그러한 경로에 대해서는 신경 쓰지 않는다.
그는 다만 노점 i에서 노점 j로 그가 노점 j에서 상을 받을 수 있을 때 이동할 것이고,
절대로 중간에 다른 노점을 경유해서 가는 일이 없다.
더욱이, T(i, j)는 T(j, i)와 다른 값을 가질 수도 있는데, 농부 철수가 언덕에서는 천천히 걷기 때문이다.
농부 철수는 시간 0에 노점 #1에서 출발한다. 그가 최대한 많은 상을 모을 수 있도록 도와주자.
입력
1번째 줄: 정수 N. 2번째..1+N번째 줄: i+1번째 줄은 한 개의 정수, P(i)를 포함한다. 2+N번째 줄 ~ 1+N+N2번째 줄: 이 N2 개의 줄은 각각 1개의 정수 T(i, j)를 (각 노점들의 쌍(i, j)에 대해) 포함한다. 처음 N줄은 각각 T(1, 1), T(1, 2), ..., T(1, N)을 포함한다. 다음 N줄은 T(2, 1), T(2, 2), ... , T(2, N)을 포함하고, 나머지도 마찬가지이다. 각 T(i, j)값은 1 ... 1,000,000 범위이고, 대각선상의 값들 T(1, 1), T(2, 2), ..., T(N, N)는 예외인데, 값이 0이다.
출력
1번째 줄: 한 개의 정수 철수가 모을 수 있는 가능한 최대의 상의 개수를 출력한다.
예제
4
13
9
19
3
0
10
20
3
4
0
11
2
1
15
0
12
5
5
13
0
3
로그인해야 코드를 작성할 수 있어요.