У Васи есть n предметов, которые лежат в ряд. Предметы последовательно пронумерованы числами от 1 до n таким образом, что самый левый предмет имеет номер 1, самый правый — номер n. Каждый предмет имеет свой вес, i-тый из них весит wi килограмм.
Васе нужно собрать все эти предметы, однако он не будет делать этого сам, а использует своего нового робота. У робота есть две разные руки — левая и правая. Робот может последовательно выполнять действия:
- Взять левой рукой самый левый из предметов, затратив на это wi · l единиц энергии (где wi — вес самого левого предмета, l — заданный параметр), если предыдущее действие было таким же (левой рукой), то робот тратит дополнительные Ql единиц энергии.
- Взять правой рукой самый правый из предметов, затратив на это wj · r единиц энергии (где wj — вес самого правого предмета, r — заданный параметр), если предыдущее действие было таким же (правой рукой), то робот тратит дополнительные Qr единиц энергии.
Разумеется, Вася хочет запрограммировать робота так, чтобы тот потратил как можно меньше энергии. С этой задачей он и обратился за помощью к вам. Ваша задача — найти минимальное количество энергии, которое потратит робот, чтобы собрать все предметы.
Выходные данные
В единственной строке выведите целое число — ответ на задачу.
Примечание
Рассмотрим первый пример. Так как l = r, мы можем просто по очереди брать по одному предмету с левой, с правой и потом опять с левой стороны. В итоге будет затрачено 4·42 + 4·99 + 4·3 = 576 единиц энергии.
Второй пример. Оптимальное решение — взять один предмет справа, затем один предмет слева и затем два предмета справа. В итоге будет затрачено (2·4) + (7·1) + (2·3) + (2·2 + 9) = 34 единицы энергии.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
3 4 4 19 1
42 3 99
|
576
|
|
2
|
4 7 2 3 9
1 2 3 4
|
34
|