После того как Boboniu закончил строительство своего Jianghu, он занимался кунг-фу на этих горах каждый день.
Boboniu разработал карту для своих \(n\) гор. Он использовал \(n-1\) дорогу чтобы соединить все \(n\) гор. Все горы связны с помощью дорог.
Для \(i\)-й горы, Boboniu оценил скучность кунг-фу на ней как \(t_i\). Он также оценил высоту каждой горы как \(h_i\).
Путь это такая последовательность гор \(M\), что для всех \(i\) (\(1 \le i < |M|\)), существует дорога между \(M_i\) и \(M_{i+1}\). Boboniu считает путь испытанием если для всех \(i\) (\(1\le i<|M|\)), \(h_{M_i}\le h_{M_{i+1}}\).
Boboniu хочет разделить все \(n-1\) дорог на несколько испытаний. Обратите внимание, что каждая дорога должна встречаться ровно в одном испытании, но гора может встречаться в нескольких испытаниях.
Boboniu хочет минимизировать суммарную скучность всех испытаний. Скучность испытания \(M\) это сумма скучностей всех гор в ней, т.е. \(\sum_{i=1}^{|M|}t_{M_i}\).
Он попросил вас найти минимальную возможную суммарную скучность всех испытаний. В награду за вашу работу, вы станете охранником в его Jianghu.
Выходные данные
Выведите одно целое число: минимальную возможную суммарную скучность всех испытаний.
Примечание
В первом примере:
На картинке, чем светлее точка, тем выше гора, которую она представляет. Одно из лучших разделений это:
- Испытание \(1\): \(3 \to 1 \to 2\)
- Испытание \(2\): \(5 \to 2 \to 4\)
Суммарно скучность для Boboniu равна \((30 + 40 + 10) + (20 + 10 + 50) = 160\). Можно показать, что это является минимальной возможной скучностью.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
40 10 30 50 20
2 3 2 3 1
1 2
1 3
2 4
2 5
|
160
|
|
2
|
5
1000000 1 1 1 1
1000000 1 1 1 1
1 2
1 3
1 4
1 5
|
4000004
|
|
3
|
10
510916 760492 684704 32545 484888 933975 116895 77095 127679 989957
402815 705067 705067 705067 623759 103335 749243 138306 138306 844737
1 2
3 2
4 3
1 5
6 4
6 7
8 7
8 9
9 10
|
6390572
|