You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

有 $n$ 个人，编号1~n。

$n$ 个人排成一排， 从左到右第 $i$ 个人的编号为 $p_i$。

你的目标是将这些人按编号升序排好，最左边的编号最小，最右边的编号最大。

你可以以任意顺序重复以下三种操作任意次：

1. 选择一个数 $i$，支付 $a_i$ 的代价，将编号为 $i$ 的人移动到任意位置。
2. 选择一个数 $i$，支付 $b_i$ 的代价，将编号为 $i$ 的人移动到最左边。
3. 选择一个数 $i$，支付 $c_i$ 的代价，将编号为 $i$ 的人移动到最右边。

问最小代价是多少，才能使得这些人从左到右按编号升序排列。

输入格式

第一行一个整数 $n$。

第二行 $n$ 个整数 $p_1, p_2, \dots , p_n$。

接下来 $n$ 行，每行 3 个整数，表示 $a_i, b_i, c_i$。

输出格式

一个整数表示最小代价。

样例输入1

3
3 1 2
9 3 5
8 6 4
9 4 6

样例输出1

6

样例解释1

将编号为3的人移动到最右边，花费代价$c_3=6$。

样例输入2

6
2 6 5 3 4 1
10 8 16
30 2 10
10 17 8
11 27 22
8 6 5
15 29 2

样例输出2

15

花费 $b_1=8$ 将 编号为1的人移动到最左边。126534

花费 $c_5=5$ 将 编号为5的人移动到最右边。126345

花费 $c_6=2$ 将 编号为6的人移动到最右边。123456

数据范围

$1 \le n \le 2*10^5; 1\le p_i \le n; 1\le a_i, b_i, c_i \le 10^9$

$p$ 为1~n的排列。