• محدودیت زمان: ۱ ثانیه
• محدودیت حافظه: ۲۵۶ مگابایت

---

Snapp Food wants to praise the best restaurants according to their in-app scores. Each restaurant has introduced and sent its representative to Snapp Food’s center.

There are $n$ representatives who are given ID numbers $1$ through $n$, standing in a row from left to right. Initially, the ID number of the $i$-th person from the left is $p_i$.

Snapp Food wants you to rearrange the representatives in ascending order of the ID number from left to right, by repeatedly doing the three kinds of operations below. You can do these operations any number of times (possibly zero) in any order:

• Choose an integer $i(1 \leq i \leq n$), pay the cost $a_i$, and move representative $i$(the person with the ID number $i$) to any position of your choice.
• Choose an integer $i(1 \leq i \leq n$), pay the cost $b_i$, and move representative $i$ to the left end of the row.
• Choose an integer $i(1 \leq i \leq n$), pay the cost $b_i$, and move representative $i$ to the right end of the row.

Minimize the total cost you pay before achieving the objective.

input

The first line of the test case is the number of representatives $n$.

In the next line of the input, the representative IDs ($p_i$) are separated by space.

The following $n$ lines, each includes the three aforementioned costs: $a_i, b_i, c_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)$$

all values in input are integers.

output

Print the minimum total cost you need to pay before achieving the objective.

example

sample input 1

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

sample output 1

6