매년, 농부 철수는 품평회에 참가하는 것을 좋아한다.

이번 품평회에는 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에서 출발한다. 그가 최대한 많은 상을 모을 수 있도록 도와주자.

품평회 timer 1s memory 256MB

품평회 1s 256MB