背景

译自 NWERC 2018 F 题。

题目描述

经典电子游戏 “Prince of Python” 包含 $n$ 个关卡，编号从 $1$ 到 $n$。你要以尽可能快的速度通关这个游戏，可以按任意顺序完成所有关卡。

进入每个关卡时，你可以装备 $n+1$ 个魔法物品之一。一开始，你的物品栏里只有物品 $0$。每当你通关一个关卡，就可以保留与该关卡编号相同的物品。例如，完成第 $5$ 关后，你会获得强大的 “Gauntlet of 5 Fingers”，之后就可以装备它，而不必只用一开始那把不太受欢迎的 “Sword of 0 Damage”。

通关某个关卡所需时间取决于你带入该关卡的物品。编号更高的物品更强大，因此如果按正常规则游玩，使用编号更高的物品通关某关所需时间总是不超过使用编号更低的物品。

不过，每个关卡还留下了一个开发者设置的捷径。某一关的捷径可以通过以非常规方式使用某个特定物品来进入。通过这种方式，你可以像使用其他任何物品一样快，甚至更快地完成该关。

你通关整个游戏最少需要多少时间？

输入格式

输入包括：

• 一行一个整数 $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$），分别表示第 $i$ 关的捷径物品，以及使用捷径通关第 $i$ 关的时间。

该行剩余部分包含 $n+1$ 个整数 $a_{i,0},\ldots,a_{i,n}$（$10^9\ge a_{i,0}\ge a_{i,1}\ge\cdots\ge a_{i,n}\ge s_i$），其中 $a_{i,j}$ 表示按正常规则使用物品 $j$ 通关第 $i$ 关的时间。

输出格式

输出以任意顺序完成游戏所有关卡所需的最短时间。

3
1 1 40 30 20 10
3 1 95 95 95 10
2 1 95 50 30 20

91

4
4 4 5 5 5 5 5
4 4 5 5 5 5 5
4 4 5 5 5 5 5
4 4 5 5 5 5 5

17

提示

【数据规模与约定】

具体限制见输入格式。