Маленькая Мишка — большая путешественница. В каких только странах она не побывала! После долгих раздумий о том, куда бы поехать в этом году, выбор её пал на XXX — прекрасную, но малоизвестную северную страну.
Вот несколько интересных фактов об этой стране:
- В состав XXX входят n городов, k из которых (только представьте себе!) являются столицами.
- Все города этой страны красивы, но по-разному. Красота i-го города описывается величиной ci.
- Все города последовательно соединены дорогами, включая 1-й и n-й город, образуя замкнутый маршрут 1 — 2 — ... — n — 1. Формально, для каждого 1 ≤ i < n существует дорога между городами i и i + 1, и еще одна между городами 1 и n.
- Каждый город-столица напрямую соединен дорогами со всеми остальными городами. Формально, если город x — столица, то для каждого 1 ≤ i ≤ n, i ≠ x, существует дорога между городами x и i.
- Между любыми двумя городами существует не более одной дороги.
- Стоимость проезда между городами напрямую зависит от показателей их красоты. Так, если между городами i и j существует дорога, то стоимость проезда по ней равна ci·cj.
Мишка уже начала собираться в путешествие, но ещё не определилась со своим маршрутом, а потому попросила вас помочь ей оценить суммарную стоимость проезда по всем дорогам XXX. Формально, по всем различным парам городов a и b (a < b), таких, что a и b соединены дорогой, требуется посчитать сумму произведений ca·cb. Поможете ей?
Выходные данные
Выведите единственное целое число — суммарную стоимость проезда по всем существующим дорогам в XXX.
Примечание
Рисунок, описывающий первый пример:
Несложно посчитать, что суммарная стоимость дорог равна 17.
Рисунок, описывающий второй пример:
Несложно посчитать, что суммарная стоимость дорог равна 71.
Примеры
| № | Входные данные | Выходные данные |
|
1
|
4 1
2 3 1 2
3
|
17
|
|
2
|
5 2
3 5 2 2 4
1 4
|
71
|