Є \(N\) людей, яким присвоєні ідентифікаційні номери від 1 до \(N\), які стоять в ряд. Спочатку ідентифікаційний номер \(i\)-ї людини — \(P_i\). Ваша мета — переставити людей у ​​порядку зростання ідентифікаційного номера, багаторазово виконуючи три види операцій, наведені нижче. Ви можете виконувати ці операції будь-яку кількість разів (можливо, нуль) у будь-якому порядку.

• Виберіть ціле число \(i\) \((1 \leq i \leq N)\), сплатіть вартість \(A_i\), і перемістіть людину \(i\) (особу з ідентифікаційним номером \(i\)) на будь-яку позицію на ваш вибір.

• Виберіть ціле число \(i\) (\(1 \leq i \leq N\)), сплатіть вартість \(B_i\), і перемістіть людину \(i\) в лівий кінець рядка.

• Виберіть ціле число \(i\) (\(1 \leq i \leq N\)), сплатіть вартість \(C_i\), і перемістіть людину \(i\) у правий кінець рядка.

Мінімізуйте загальні витрати, які ви сплачуєте, перш ніж досягти мети.

Формат вхідних даних

Перший рядок містить ціле число \(N\) (\(1 \le N \le 2 \times 10^5\))

Наступний  рядок містить \(N\) цілих чисел \(P_i\) (\(1 \le A_i \le N\))

Наступні  \(N\) рядків містять цілі числа \(A_i, B_i, C_i\) (\(1 \le A_i, B_i,C_i \le 10^9\))

Формат вихідних даних

У вихідний потік виведіть мінімальну загальну вартість, яку потрібно сплатити, перш ніж досягти мети.

Примітка

До прикладу 1:

Ви можете переставити людей у ​​порядку зростання ідентифікаційного номера, заплативши вартість \(C_3=6\), щоб перемістити людину 3 у кінець. Немає способу переставити людей дешевше, тому відповідь 6.

Приклад вхідних даних

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

Приклад вихідних даних

6

Приклад вхідних даних

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

Приклад вихідних даних

15

Приклад вхідних даних

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

Приклад вихідних даних

15865