가장 빠른 스피드런

고전 비디오 게임 "Prince of Python"에는 1번부터 $n$번까지 번호가 붙은 $n$개의 레벨이 있다. 모든 레벨을 가능한 한 빠르게 깨는 스피드런을 하려고 한다. 레벨은 원하는 순서로 깨도 된다.

각 레벨에는 $n + 1$개의 마법 아이템 중 하나를 가지고 들어간다. 처음에는 인벤토리에 아이템 0만 있다. 레벨을 깨면 그 레벨과 번호가 같은 아이템을 얻어 계속 보유한다. 예를 들어 5번 레벨을 깨면 5개의 손가락을 가진 건틀릿을 얻고, 이후에는 처음 가진 0 피해의 검 대신 장착할 수 있다.

레벨을 깨는 데 걸리는 시간은 들어갈 때 가지고 있던 아이템에 따라 다르다. 번호가 높은 아이템일수록 강하므로, 규칙대로 플레이하면 번호가 높은 아이템이 번호가 낮은 아이템보다 빠르거나 같다.

하지만 각 레벨에는 개발자가 남겨 둔 지름길이 있다. 지름길은 특정 아이템을 비정상적인 방식으로 사용하면 열린다. 지름길을 쓰면 다른 어떤 아이템을 쓸 때보다 같거나 더 빠르게 레벨을 깰 수 있다.

모든 레벨을 깨는 데 걸리는 최소 시간은 얼마인가?

입력은 다음과 같다.

• 첫 줄에 정수 $n$ ($1 \le n \le 2500$)이 주어진다. 레벨의 개수이다.
• 이후 $n$개의 줄이 각 레벨을 설명한다.
  $i$번째 줄은 두 정수 $x_i$와 $s_i$ ($0 \le x_i \le n$, $1 \le s_i \le 10^9$)로 시작한다. $x_i$는 $i$번 레벨의 지름길 아이템이고, $s_i$는 지름길을 썼을 때 $i$번 레벨을 깨는 시간이다. 줄의 나머지에는 $n + 1$개의 정수 $a_{i,0}, \ldots, a_{i,n}$ ($10^9 \ge a_{i,0} \ge a_{i,1} \ge \ldots \ge a_{i,n} \ge s_i$)이 있다. $a_{i,j}$는 규칙대로 아이템 $j$를 사용해 $i$번 레벨을 깨는 시간이다.

모든 레벨을 순서와 상관없이 깨는 데 필요한 최소 시간을 출력한다.