经典电子游戏“Prince of Python”包含 $n$ 个关卡，编号从 $1$ 到 $n$。你打算通过尽可能快地完成所有关卡来速通这款游戏，并且你可以以任何你想要的顺序完成它们。

你进入每个关卡时都会装备 $n+1$ 种魔法物品中的一种。起初，你的背包里只有物品 $0$。一旦你通关了一个关卡，你就可以保留与该关卡编号相同的物品。例如，在完成第 $5$ 关后，你将获得强大的“五指护手”（Gauntlet of 5 Fingers），此后你可以装备它，而不是你一开始就拥有的、评价较低的“零伤害之剑”（Sword of 0 Damage）。

根据你携带的物品不同，完成一个关卡所需的时间也不同。编号越大的物品越强大，因此按照规则游玩时，使用编号较大的物品完成关卡的速度至少与使用编号较小的物品一样快。

然而，每个关卡也都有开发者留下的捷径。通过以非常规方式使用特定物品，可以进入关卡的捷径。通过这种方式，你可以以与使用任何其他物品一样快、甚至更快的速度完成关卡。

完成游戏中的所有关卡需要多长时间？

输入格式

输入包含： 一行包含一个整数 $n$ ($1 \le n \le 2\,500$)，表示关卡数量。 $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}, \dots, a_{i,n}$ ($10^9 \ge a_{i,0} \ge a_{i,1} \ge \dots \ge a_{i,n} \ge s_i$)，其中 $a_{i,j}$ 表示使用物品 $j$ 按规则完成关卡 $i$ 所需的时间。

输出格式

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

样例

样例输入 1

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

样例输出 1

91

样例输入 2

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

样例输出 2

17