Середина 2018-го года и на границе Краснокаменска, что в Забайкальском крае, Мария Степановна хочет арендовать три электронных табло для обращения внимания жителей на важную проблему.
Вдоль дороги в один ряд стоят \(n\) электронных табло, причем на \(i\)-м табло текст может отображаться только со шрифтом размера \(s_i\). Мария Степановна хочет арендовать три таких табло с индексами \(i < j < k\), что размер шрифта строго увеличиваются при проезде в определенную сторону, а именно, должно выполняться \(s_i < s_j < s_k\).
Стоимость аренды \(i\)-го табло равна \(c_i\). Определите, какую минимальную стоимость должна заплатить Мария Степановна.
Выходные данные
Если не существует трех подходящих табло, выведите -1. В противном случае, выведите одно целое число — минимальную стоимость аренды трех табло с индексами \(i < j < k\) таких, что \(s_i < s_j < s_k\).
Примечание
В первом примере можно, например, выбрать табло \(1\), \(4\) и \(5\), так как \(s_1 < s_4 < s_5\) (\(2 < 4 < 10\)), а суммарная стоимость равна \(40 + 10 + 40 = 90\).
Во втором примере невозможно выбрать подходящую тройку табло, поэтому ответ -1.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
5
2 4 5 4 10
40 30 20 10 40
|
90
|
|
2
|
3
100 101 100
2 4 5
|
-1
|
|
3
|
10
1 2 3 4 5 6 7 8 9 10
10 13 11 14 15 12 13 13 18 13
|
33
|