问题说明

有 $N$ 个人，他们的ID号从 $1$ 到 $N$，站在从左到右排列的队列中。最初，从左边数第 $i$ 个人的ID号是 $P_i$。

你的目标是将这些人按照ID号从左到右升序重新排列，通过反复执行以下三种操作之一来实现。你可以以任意次数（可能为零）以任意顺序执行这些操作。

• 选择一个整数 $i\\ (1 \\leq i \\leq N)$，支付费用 $A_i$，并将第 $i$ 个人（ID号为 $i$ 的人）移动到你选择的任何位置。
• 选择一个整数 $i\\ (1 \\leq i \\leq N)$，支付费用 $B_i$，并将第 $i$ 个人移到队列的最左边。
• 选择一个整数 $i\\ (1 \\leq i \\leq N)$，支付费用 $C_i$，并将第 $i$ 个人移到队列的最右边。

在实现目标之前，使你支付的总费用最小化。

约束条件

• $1 \\leq N \\leq 2 \\times 10^5$
• $1 \\leq P_i \\leq N$
• $1 \\leq A_i,B_i,C_i \\leq 10^9$
• $P_i \\neq P_j\\ (i \\neq j)$
• 输入中的所有值都是整数。

输入

输入以以下格式从标准输入给出：

$N$ $P_1$ $P_2$ $\\ldots$ $P_N$ $A_1$ $B_1$ $C_1$ $A_2$ $B_2$ $C_2$ $\\vdots$ $A_N$ $B_N$ $C_N$

输出

打印在实现目标之前你需要支付的最小总费用。

示例输入1

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

示例输出1

6

你可以通过支付费用 $C_3=6$ 将第 $3$ 个人移到最右边，按照ID号的升序重新排列这些人。

没有更便宜的重新排列人的方法，所以答案是 $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$ 个人移到最左边；
• 支付费用 $C_5=5$ ，将第 $5$ 个人移到最右边；
• 支付费用 $C_6=2$ ，将第 $6$ 个人移到最右边。

示例输入3

9
3 8 4 7 6 9 1 5 2
7976 3696 9706
768 8807 8521
1133 8683 7120
1189 3331 2259
900 7451 1159
6126 2639 7107
5540 8253 2891
8417 4220 9091
8732 1417 1540

示例输出3

15865

示例输入4

12
11 9 1 12 2 7 3 5 10 4 6 8
3960 3158 9029
6521 6597 7581
5688 2299 2123
4946 4298 9122
394 4350 9142
3098 7151 2039
8525 3758 6155
6970 3658 9353
9780 1778 3608
6065 5562 923
9701 5524 6482
9395 6016 705

示例输出4

20637